Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs
<|reference_start|>Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs: We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph.In the robust setting, the input is not given as a set of sites in the plane, but rather as an abstract graph. The input may or may not be realizable as a unit disk graph or a transmission graph. If the graph is realizable, the algorithm is guaranteed to give the correct answer. If not, the algorithm will either give a correct answer or correctly state that the input is not of the required type.<|reference_end|>
@article{klost2024robust,
    title={Robust Algorithms for Finding Triangles and Computing the Girth in Unit
  Disk and Transmission Graphs},
    author={Katharina Klost and Wolfgang Mulzer},
    journal={arXiv preprint arXiv:2405.01180},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01180},
    primaryClass={cs.CG}
}