Document Open Access Logo

Triangles and Girth in Disk Graphs and Transmission Graphs

Authors Haim Kaplan, Katharina Klost, Wolfgang Mulzer , Liam Roditty, Paul Seiferth, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.64.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Haim Kaplan
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Katharina Klost
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Liam Roditty
  • Department of Computer Science, Bar Ilan University, Ramat Gan 5290002, Israel
Paul Seiferth
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Micha Sharir
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Funding

Supported in part by grant 1367/2016 from the German-Israeli Science Foundation (GIF).
  • Mulzer, Wolfgang: Partially supported by ERC STG 757609.
  • Seiferth, Paul: Partially supported by DFG grant MU/3501/1.
  • Sharir, Micha: Partially supported by ISF Grant 892/13, the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), the Blavatnik Research Fund in Computer Science at Tel Aviv University, and the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University.

Acknowledgements

We like to thank Günther Rote and Valentin Polishchuk for helpful comments.

Cite As Get BibTex

Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Triangles and Girth in Disk Graphs and Transmission Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.64

Abstract

Let S subset R^2 be a set of n sites, where each s in S has an associated radius r_s > 0. The disk graph D(S) is the undirected graph with vertex set S and an undirected edge between two sites s, t in S if and only if |st| <= r_s + r_t, i.e., if the disks with centers s and t and respective radii r_s and r_t intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph T(S) is the directed graph with vertex set S and a directed edge from a site s to a site t if and only if |st| <= r_s, i.e., if t lies in the disk with center s and radius r_s.
We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in D(S) and in T(S). These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in D(S) and in T(S) can be found in O(n log n) expected time, and that the (weighted) girth of D(S) can be found in O(n log n) expected time. For this, we develop new tools for batched range searching that may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Graph algorithms analysis
Keywords
  • disk graph
  • transmission graph
  • triangle
  • girth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and Counting Given Length Cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  2. Mark Bergde Berg, Otfried Cheong, Marc van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, third edition, 2008. Google Scholar
  3. Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer. Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended. Algorithmica, 61(3):674-693, 2011. Google Scholar
  4. Kevin Buchin and Wolfgang Mulzer. Delaunay triangulations in O(sort(n)) time and more. J. ACM, 58(2):6:1-6:27, 2011. Google Scholar
  5. Timothy M. Chan. Geometric Applications of a Randomized Optimization Technique. Discrete Comput. Geom., 22(4):547-567, 1999. Google Scholar
  6. Timothy M. Chan. A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions. Discrete Comput. Geom., 56(4):860-865, December 2016. Google Scholar
  7. Hsien-Chih Chang and Hsueh-I Lu. Computing the Girth of a Planar Graph in Linear Time. SIAM J. Comput., 42(3):1077-1094, 2013. Google Scholar
  8. Bernard Chazelle and Wolfgang Mulzer. Computing Hereditary Convex Structures. Discrete Comput. Geom., 45(4):796-823, 2011. Google Scholar
  9. William S. Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk. Recognizing a DOG is Hard, But Not When It is Thin and Unit. In Proc. 8th FUN, pages 16:1-16:12, 2016. Google Scholar
  10. François GallLe Gall. Powers of tensors and fast matrix multiplication. In Proc. 39th Internat. Symp. Symbolic and Algebraic Comput. (ISSAC), pages 296-303, 2014. Google Scholar
  11. Sariel Har-Peled. Geometric approximation algorithms. American Mathematical Society, 2008. Google Scholar
  12. Alon Itai and Michael Rodeh. Finding a Minimum Circuit in a Graph. SIAM J. Comput., 7(4):413-423, 1978. Google Scholar
  13. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Spanners and Reachability Oracles for Directed Transmission Graphs. In Proc. 31st Int. Sympos. Comput. Geom. (SoCG), pages 156-170, 2015. Google Scholar
  14. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Spanners for Directed Transmission Graphs. SIAM J. Comput., 47(4):1585-1609, 2018. Google Scholar
  15. Jakub Ła̧cki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n) time. In Proc. 19th Annu. European Sympos. Algorithms (ESA), pages 155-166, 2011. Google Scholar
  16. Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, and Oren Weimann. Minimum Cut of Directed Planar Graphs in O(n log log n) Time. In Proc. 29th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 477-494, 2018. Google Scholar
  17. Christos H. Papadimitriou and Mihalis Yannakakis. The Clique Problem for Planar Graphs. Inform. Process. Lett., 13(4/5):131-133, 1981. Google Scholar
  18. Valentin Polishchuk. Personal communication, 2017. Google Scholar
  19. Liam Roditty and Virginia Vassilevska Williams. Minimum Weight Cycles and Triangles: Equivalences and Algorithms. In Proc. 52nd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 180-189, 2011. Google Scholar
  20. Dan E. Willard and George S. Lueker. Adding Range Restriction Capability to Dynamic Data Structures. J. ACM, 32(3):597-617, 1985. Google Scholar
  21. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM, 65(5):27:1-27:38, 2018. Google Scholar
  22. Huacheng Yu. An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. In Proc. 42nd Internat. Colloq. Automata Lang. Program. (ICALP), pages 1094-1105, 2015. Google Scholar
  23. Raphael Yuster. A shortest cycle for each vertex of a graph. Inform. Process. Lett., 111(21-22):1057-1061, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact