Document Open Access Logo

Recognition and Complexity of Point Visibility Graphs

Authors Jean Cardinal, Udo Hoffmann

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.171.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Jean Cardinal
Udo Hoffmann

Cite As Get BibTex

Jean Cardinal and Udo Hoffmann. Recognition and Complexity of Point Visibility Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 171-185, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.171

Abstract

A point visibility graph is a graph induced by a set of points in the plane, where every vertex corresponds to a point, and two vertices are adjacent whenever the two corresponding points are visible from each other, that is, the open segment between them does not contain any other point of the set.

We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mnev and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs.

Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.

Subject Classification

Keywords
  • point visibility graphs
  • recognition
  • existential theory of the reals

Metrics

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

References

  1. James Abello and Krishna Kumar. Visibility graphs and oriented matroids. Discrete & Computational Geometry, 28(4):449-465, 2002. Google Scholar
  2. Karim A. Adiprasito, Arnau Padrol, and Louis Theran. Universality theorems for inscribed polytopes and Delaunay triangulations. ArXiv e-prints, 2014. Google Scholar
  3. Daniel Bienstock. Some provably hard crossing number problems. Discrete and Computational Geometry, 6:443-459, 1991. Google Scholar
  4. John Canny. Some algebraic and geometric computations in PSPACE. In STOC '88, pages 460-467. ACM, 1988. Google Scholar
  5. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008 (third edition). Google Scholar
  6. Subir K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. In 1st Scandinavian Workshop on Algorithm Theory (SWAT), pages 96-104, 1988. Google Scholar
  7. Subir K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry, 17(2):143-162, 1997. Google Scholar
  8. Subir K. Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, 2007. Google Scholar
  9. Subir K. Ghosh and Partha P. Goswami. Unsolved problems in visibility graphs of points, segments, and polygons. ACM Computing Surveys (CSUR), 46(2):22, 2013. Google Scholar
  10. Subir K. Ghosh and Bodhayan Roy. Some results on point visibility graphs. In Algorithms and Computation (WALCOM), volume 8344 of Lecture Notes in Computer Science, pages 163-175. Springer, 2014. Google Scholar
  11. Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. The intrinsic spread of a configuration in ℝ^d. Journal of the American Mathematical Society, pages 639-651, 1990. Google Scholar
  12. Branko Grünbaum. Convex Polytopes, volume 221 (2nd ed.) of Graduate Texts in Mathematics. Springer-Verlag, 2003. Google Scholar
  13. Michael Kapovich and John J. Millson. Universality theorems for configuration spaces of planar linkages. Topology, 41:1051-1107, 2002. Google Scholar
  14. Jan Kára, Attila Pór, and David R. Wood. On the chromatic number of the visibility graph of a set of points in the plane. Discrete & Computational Geometry, 34(3):497-506, 2005. Google Scholar
  15. Jan Kratochvíl and Jirí Matoušek. Intersection graphs of segments. Journal of Combinatorial Theory. Series B, 62(2):289-315, 1994. Google Scholar
  16. Jan Kynčl. Simple realizability of complete abstract topological graphs in P. Discrete and Computational Geometry, 45(3):383-399, 2011. Google Scholar
  17. Tomás Lozano-Pérez and Michael A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 22(10):560-570, October 1979. Google Scholar
  18. Jiří Matoušek. Intersection graphs of segments and ∃ℝ. ArXiv e-prints, 2014. Google Scholar
  19. Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, 103(1):114 - 143, 2013. Google Scholar
  20. Nicolai E. Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and geometry—Rohlin seminar, pages 527-543. Springer, 1988. Google Scholar
  21. Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Google Scholar
  22. Joseph O'Rourke and Ileana Streinu. Vertex-edge pseudo-visibility graphs: Characterization and recognition. In Symposium on Computational Geometry, pages 119-128, 1997. Google Scholar
  23. Michael S. Payne, Attila Pór, Pavel Valtr, and David R. Wood. On the connectivity of visibility graphs. Discrete & Computational Geometry, 48(3):669-681, 2012. Google Scholar
  24. Attila Pór and David R. Wood. On visibility and blockers. JoCG, 1(1):29-40, 2010. Google Scholar
  25. Jürgen Richter-Gebert. Mnëv’s universality theorem revisited. In Proceedings of the Séminaire Lotharingien de Combinatoire, pages 211-225, 1995. Google Scholar
  26. Bodhayan Roy. Point visibility graph recognition is NP-hard. ArXiv e-prints, 2014. Google Scholar
  27. Marcus Schaefer. Complexity of some geometric and topological problems. In 17th International Symposium on Graph Drawing (GD), pages 334-344, 2009. Google Scholar
  28. Marcus Schaefer. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory. Springer, 2012. Google Scholar
  29. Peter W. Shor. Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift, 4:531-554, 1991. Google Scholar
  30. Karl Georg Christian Staudt. Geometrie der Lage. Verlag von Bauer und Raspe, 1847. Google Scholar
  31. Ileana Streinu. Non-stretchable pseudo-visibility graphs. Comput. Geom., 31(3):195-206, 2005. 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