LIPIcs.SWAT.2022.7.pdf
- Filesize: 0.7 MB
- 13 pages
Document
On the Visibility Graphs of Pseudo-Polygons: Recognition and Reconstruction
Authors
Matt Gibson-Lopez 
,
-
Part of:
Volume:
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-22
File
Document Identifiers
Author Details
Cite As Get BibTex
Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, and Qing Wang. On the Visibility Graphs of Pseudo-Polygons: Recognition and Reconstruction. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.7
Abstract
We give polynomial-time algorithms that solve the pseudo-polygon visibility graph recognition and reconstruction problems. Our algorithms are based on a new characterization of the visibility graphs of pseudo-polygons.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Pseudo-Polygons
- Visibility Graph Recognition
- Visibility Graph Reconstruction
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, and Pedro Ramos. Decomposition of multiple coverings into more parts. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 302-310, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1496770.1496804.
- Boris Aronov, Esther Ezra, and Micha Sharir. Small-size epsilon-nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248-3282, July 2010. URL: https://doi.org/10.1137/090762968.
- Seung-Hak Choi, Sung Yong Shin, and Kyung-Yong Chwa. Characterizing and recognizing the visibility graph of a funnel-shaped polygon. Algorithmica, 14(1):27-51, 1995. URL: https://doi.org/10.1007/BF01300372.
- Hazel Everett and Derek G. Corneil. Negative results on characterizing visibility graphs. Comput. Geom., 5:51-63, 1995. URL: https://doi.org/10.1016/0925-7721(95)00021-Z.
- Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, and Aravind Srinivasan. Approximating the domatic number. SIAM J. Comput., 32(1):172-195, January 2003. URL: https://doi.org/10.1137/S0097539700380754.
-
Subir Kumar Ghosh. On recognizing and characterizing visibility graphs of simple polygons. In SWAT, pages 96-104, 1988.
- Subir Kumar Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry, 17(2):143-162, 1997. URL: https://doi.org/10.1007/BF02770871.
- Subir Kumar Ghosh and Partha P. Goswami. Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv., 46(2):22, 2013. URL: https://doi.org/10.1145/2543581.2543589.
-
Matt Gibson, Erik Krohn, and Qing Wang. A characterization of visibility graphs for pseudo-polygons. In ESA, pages 607-618, 2015.
- Joseph O'Rourke and Ileana Streinu. Vertex-edge pseudo-visibility graphs: Characterization and recognition. In Symposium on Computational Geometry, pages 119-128, 1997. URL: https://doi.org/10.1145/262839.262915.
- Joseph O'Rourke and Ileana Streinu. The vertex-edge visibility graph of a polygon. Computational Geometry, 10(2):105-120, 1998. URL: https://doi.org/10.1016/S0925-7721(97)00011-4.
- G. Srinivasaraghavan and Asish Mukhopadhyay. A new necessary condition for the vertex visibility graphs of simple polygons. Discrete & Computational Geometry, 12:65-82, 1994. URL: https://doi.org/10.1007/BF02574366.
- Ileana Streinu. Non-stretchable pseudo-visibility graphs. Comput. Geom., 31(3):195-206, 2005. URL: https://doi.org/10.1016/j.comgeo.2004.12.003.
- Kasturi R. Varadarajan. Epsilon nets and union complexity. In Symposium on Computational Geometry, pages 11-16, 2009. URL: https://doi.org/10.1145/1542362.1542366.