Abstract
In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to a characterization of vertex-edge visibility graphs given by O’Rourke and Streinu.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., Ramos, P.: Decomposition of multiple coverings into more parts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 302–310. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Aronov, B., Ezra, E., Sharir, M.: Small-size epsilon-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)
Choi, S.-H., Shin, S.Y., Chwa, K.-Y.: Characterizing and recognizing the visibility graph of a funnel-shaped polygon. Algorithmica 14(1), 27–51 (1995)
Everett, H., Corneil, D.G.: Negative results on characterizing visibility graphs. Comput. Geom. 5, 51–63 (1995)
Feige, U., Halldórsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32(1), 172–195 (2003)
Ghosh, S.K.: On recognizing and characterizing visibility graphs of simple polygons. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 96–104. Springer, Heidelberg (1988)
Ghosh, S.K.: On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry 17(2), 143–162 (1997)
Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv. 46(2), 22 (2013)
O’Rourke, J., Streinu, I.: Vertex-edge pseudo-visibility graphs: Characterization and recognition. In: Symposium on Computational Geometry, pp. 119–128 (1997)
O’Rourke, J., Streinu, I.: The vertex-edge visibility graph of a polygon. Computational Geometry 10(2), 105–120 (1998)
Srinivasaraghavan, G., Mukhopadhyay, A.: A new necessary condition for the vertex visibility graphs of simple polygons. Discrete & Computational Geometry 12, 65–82 (1994)
Streinu, I.: Non-stretchable pseudo-visibility graphs. Comput. Geom. 31(3), 195–206 (2005)
Varadarajan, K.R.: Epsilon nets and union complexity. In: Symposium on Computational Geometry, pp. 11–16 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gibson, M., Krohn, E., Wang, Q. (2015). A Characterization of Visibility Graphs for Pseudo-polygons. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_51
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)