Subir K. Ghosh
Skip Abstract Section
Abstract
In this survey article, we present open problems and conjectures on visibility graphs of points, segments, and polygons along with necessary backgrounds for understanding them.
- Abel, Z., Ballinger, B., Bose, P., Collette, S., Dujmović, V., Hurtado, F., Kominers, S. D., Langerman, S., Pór, A., and Wood, D. R. 2011. Every large point set contains many collinear points or an empty pentagon. Graphs Comb. 27, 1, 47--60. Google Scholar
Digital Library
- Abello, J. and Egecioglu, O. 1993. Visibility graphs of staircase polygons with uniform step length. Int. J. Comput. Geom. Appl. 3, 27--37.Google ScholarCross Ref
- Abello, J., Egecioglu, O., and Kumar, K. 1995. Visibility graphs of staircase polygons and the weak Bruhat order, I: From visibility graphs to maximal chains. Discrete Comput. Geom. 14, 331--358.Google ScholarDigital Library
- Abello, J. and Kumar, K. 1995. Visibility graphs and oriented matroids. In Proceeding of Graph Drawing. Lecture Notes in Computer Science Series, vol. 894. Springer-Verlag, 147--158. Google ScholarDigital Library
- Abello, J. and Kumar, K. 2002. Visibility graphs and oriented matroids. Discrete Comput. Geom. 28, 449--465.Google ScholarDigital Library
- Abello, J., Lin, H., and Pisupati, S. 1992. On visibility graphs of simple polygons. Congressus Numerantium 90, 119--128.Google Scholar
- Agarwal, P. K., Alon, N., Aronov, B., and Suri, S. 1994. Can visibility graphs be represented compactly? Discrete Comput. Geom. 12, 347--365.Google ScholarDigital Library
- Aloupis, G., Ballinger, B., Collette, S., Langerman, S., Pór, A., and Wood, D. R. 2010. Blocking coloured point sets. In Proceedings of the 26th European Workshop Computational Geometry. 29--32.Google Scholar
- Alpert, H., Koch, C., and Laison, J. D. 2010. Obstacle numbers of graphs. Discrete Comput. Geom. 44, 223--244.Google ScholarDigital Library
- Andreae, T. 1992. Some results on visibility graphs. Discrete Appl. Math. 40, 5--18. Google ScholarDigital Library
- Aronov, B., Ezra, E., and Sharir, M. 2010. Small-size Îμ-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39, 3248--3282. Google ScholarDigital Library
- Asano, T., Asano, T., Guibas, L. J., Hershberger, J., and Imai, H. 1986. Visibility of disjoint polygons. Algorithmica 1, 49--63. Google ScholarDigital Library
- Avis, D. and ElGindy, H. 1983. A combinatorial approach to polygon similarity. IEEE Trans. Inf. Theory IT-2, 148--150. Google ScholarDigital Library
- Avis, D. and Rappaport, D. 1985. Computing the largest empty convex subset of a set of points. In Proceedings of the 1st ACM Symposium on Computational Geometry. 161--167. Google ScholarDigital Library
- Bárány, I. and Károlyi, G. 2001. Problems and results around the Erdös-Szekeres convex polygon theorem. In Revised Papers from the Japanese Conference on Discrete and Computational (JCDCG'00). Springer, Berlin, 91--105. Google ScholarDigital Library
- Bidokhti, N. S. 2012. On full characterizing terrain visibility graphs. Master's thesis, Department of Computing Science, University of British Columbia.Google Scholar
- Bilò, D., Disser, Y., Mihalák, M., Suri, S., Vicari, E., and Widmayer, P. 2012. Reconstructing visibility graphs with simple robots. Theor. Comput. Sci. 444, 52--59. Google ScholarDigital Library
- Bjrner, A., Vergnas, M., Sturmfels, B., White, N., and Ziegler, G. 1999. Oriented Matroids. Cambridge University Press.Google Scholar
- Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. 1989. Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36, 929--965. Google ScholarDigital Library
- Bose, P., Dean, A., Hutchinson, J. P., and Shermer, T. C. 1997. On rectangle visibility graphs. In Proceedings of the 4th International Conference on Graph Drawing. Lecture Notes in Computer Science Series, vol. 1190. Springer-Verlag, 25--44. Google ScholarDigital Library
- Bose, P., Houle, M. E., and Toussaint, G. T. 2001. Every set of disjoint line segments admits a binary tree. Discrete & Computational Geometry 26, 387--410.Google ScholarDigital Library
- Brass, P., Moser, W. O. J., and Pach, J. 2005. Research Problems in Discrete Geometry. Springer, New York.Google Scholar
- Brönnimann, H. and Goodrich, M. T. 1995. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 463--479.Google ScholarDigital Library
- Chazelle, B., Guibas, L. J., and Lee, D. 1985. The power of geometric duality. BIT 25, 76--90. Google ScholarDigital Library
- Chen, G., Hutchinson, J., Keating, K., and Shen, J. 2006. Charaterization of [1,k]-bar visibility trees. The Electronic Journal of Combinatorics 13, 1--13.Google ScholarCross Ref
- Choi, S.-H., Shin, S. Y., and Chwa, K.-Y. 1995. Characterizing and recognizing the visibility graph of a funnel-shaped polygon. Algorithmica 14, 1, 27--51.Google ScholarDigital Library
- Colley, P. 1992. Recognizing visibility graphs of unimonotone polygons. In Proceedings of the 4th Canadian Conference on Computational Geometry. 29--34.Google Scholar
- Colley, P., Lubiw, A., and Spinrad, J. 1997. Visibility graphs of towers. Comput. Geom. Theory Appl. 7, 161--172. Google ScholarDigital Library
- Coullard, C. and Lubiw, A. 1992. Distance visibility graphs. Int. J. Comput. Geom. Appl. 2, 349--362.Google ScholarCross Ref
- Das, S., Goswami, P., and Nandy, S. 2002. Testing Necessary Conditions for Recognizing Visibility Graphs of Simple Polygons. Manuscript, Indian Statistical Institute, Kolkata.Google Scholar
- de Berg, M., Cheong, O., Kreveld, M., and Overmars, M. 2008. Computational Geometry, Algorithms and Applications, 3rd Ed. Springer-Verlag. Google ScholarDigital Library
- Dean, A., Evans, W., Gethner, E., Laison, J. D., Safari, M. A., and Trotter, W. T. 2007. Bar k-visibility graphs. J. Graph Algorithms Appl. 11, 45--59.Google ScholarCross Ref
- Dean, A., Gethner, E., and Hutchinson, J. 2004. Unit bar-visibility layouts of triangulated polgyons. In Proceedings of the 11th International Conference on Graph Drawing. Lecture Notes in Computer Science Series, vol. 3383. Springer-Verlag, 111--121. Google ScholarDigital Library
- Dean, A. and Hutchinson, J. P. 1997. Rectangle-visibility representations of bipartite graphs. Discrete Appl. Math. 75, 9--25. Google ScholarDigital Library
- Dean, A. and Veytsel, N. 2003. Unit bar-visibility graphs. Congressus Numerantium 160, 161--175.Google Scholar
- Diestel, R. 2010. Graph theory. Springer.Google Scholar
- Disser, Y. 2011. Mapping Polygons. Ph.D. thesis, ETH, Zurich.Google Scholar
- Disser, Y., Bilò, D., Mihalák, M., Suri, S., Vicari, E., and Widmayer, P. 2009. On the limitations of combinatorial visibilities. In Proceedings of the 25th European Workshop on Computational Geometry. 207--210.Google Scholar
- Disser, Y., Mihalák, M., Ghosh, S. K., and Widmayer, P. 2012. Mapping a polygon with holes using compass. In Proceedings of the 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities. Lecture Notes in Computer Science, vol. 7718. Springer, 78--89.Google Scholar
- Disser, Y., Mihalák, M., and Widmayer, P. 2011. A polygon is determined by its angles. Comput. Geom. Theory Appl. 44, 418--426. Google ScholarDigital Library
- Dobkin, D. P., Edelsbrunner, H., and Overmars, M. H. 1990. Searching for empty convex polygons. Algorithmica 5, 561--571.Google ScholarCross Ref
- Duchet, P., Hamidoune, Y., Vergnas, M. L., and Meyniel, H. 1983. Representing a planar graph by vertical lines joining different levels. Discrete Math. 46, 319--321.Google ScholarDigital Library
- Dumitrescu, A., Pach, J., and Tóth, G. 2009. A note on blocking visibility between points. Geombinatorics 19, 67--73.Google Scholar
- Edelsbrunner, H., O'Rourke, J., and Seidel, R. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 341--363. Google ScholarDigital Library
- Eidenbenz, S. 2000. In-approximability of Visibility Problems on Polygons and Terrains. Ph.D. Thesis, Institute for Theoretical Computer Science, ETH, Zurich.Google Scholar
- Eidenbenz, S. 2002. In-approximability of finding maximum hidden sets on polygons and terrains. Comput. Geom. Theory Appl. 21, 139--153. Google ScholarDigital Library
- Eidenbenz, S. and Stamm, C. 2000. Maximum clique and minimum clique partition in visibility graphs. In Proceedings of IFIP International Conference on Theoretical Computer Science (TCS'00). Lecture Notes in Computer Science, vol. 1872. Springer-Verlag, 200--212. Google ScholarDigital Library
- Eidenbenz, S., Stamm, C., and Widmayer, P. 2001. Inapproximability results for guarding polygons and terrains. Algorithmica 31, 79--113.Google ScholarCross Ref
- ElGindy, H. 1985. Hierarchical Decomposition of Polygons with Applications. Ph.D. thesis, McGill University, Montreal. Google ScholarDigital Library
- Eppstein, D. 2000. Spanning trees and spanners. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds., North-Holland, 425--461.Google Scholar
- Erdös, P. 1978. Some more problems in elementary geometry. Aust. Math. Soc. Gazette 5, 52--54.Google Scholar
- Erdös, P. 1981. Some applications of graph theory and combinatorial methods to number theory and geometry. In Algebraic methods in graph theory, vols. I, II, Szeged 1978. Colloquia Mathematica Societatis Janos Bolyai. Vol. 25. North-Holland, Amsterdam, 137--148.Google Scholar
- Erdös, P. and Szekeres, G. 1935. A combinatorial problem in geometry. Compositio Mathmatica 2, 463--470.Google Scholar
- Erdös, P. and Szekeres, G. 1961. On some extremum problems in elementary geometry. Annales Universitatis Scientarium Budapestinensis de Rolando Etvs Nominatae Sectio Mathematica 3--4, 53--62.Google Scholar
- Everett, H. 1990. Visibility graph recognition. Ph. D. Thesis, University of Toronto, Toronto. Google ScholarDigital Library
- Everett, H. and Corneil, D. G. 1990. Recognizing visibility graphs of spiral polygons. J. Algorithms 11, 1--26. Google ScholarDigital Library
- Everett, H. and Corneil, D. G. 1995. Negative results on characterizing visibility graphs. Comput. Geom. Theory Appl. 5, 51--63. Google ScholarDigital Library
- Everett, H., Hoang, C. T., Kilakos, K., and Noy, M. 2000. Planar segment visibility graphs. Comput. Geom. Theory Appl. 16, 235--243. Google ScholarDigital Library
- Everett, H., Hurtado, F., and Noy, M. 1999. Stabbing information of a simple polygon. Discrete Appl. Math. 91, 67--92. Google ScholarDigital Library
- Everett, H., Lubiw, A., and O'Rourke, J. 1993. Recovery of convex hulls from external visibility graphs. In Proceedings of the 5th Canadian Conference on Computational Geometry. 309--314.Google Scholar
- Feige, U. 1998. A threshold of ln n for approximating set cover. J. ACM 45, 634--652. Google ScholarDigital Library
- Felsner, S. and Massow, M. 2007. Thickness of bar 1-visibility graphs. In Proceedings of the 14th International Conference on Graph Drawing. Lecture notes in Computer Science Series, vol. 4372. Springer-Verlag, 330--342. Google ScholarDigital Library
- Freiman, G. A. 1973. Foundations of a Structural Theory of Set Addition. Translations of Mathematical Monographs, vol. 37, American Mathematical Society, Providence.Google Scholar
- Fulek, R., Saeedi, N., and Sariöz, D. 2011. Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs. CoRR abs/1104.4656.Google Scholar
- Gerken, T. 2008. Empty convex hexagons in planar point sets. Discrete Comput. Geom. 39, 239--272. Google ScholarDigital Library
- Ghosh, S. K. 1987. Approximation algorithms for art gallery problems. In Proceedings of the Canadian Information Processing Society Congress. 429--434.Google Scholar
- Ghosh, S. K. 1988. On recognizing and characterizing visibility graphs of simple polygons. In Proceedings of the Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, Springer-Verlag, 96--104. Google ScholarDigital Library
- Ghosh, S. K. 1997. On recognizing and characterizing visibility graphs of simple polygons. Discrete Comput. Geom. 17, 143--162.Google ScholarDigital Library
- Ghosh, S. K. 2007. Visibility Algorithms in the Plane. Cambridge University Press. Google ScholarDigital Library
- Ghosh, S. K. 2010a. Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158, 718--722. Google ScholarDigital Library
- Ghosh, S. K. 2010b. Approximation algorithms for art gallery problems in polygons and terrains. In Proceedings of the 4th International Workshop on Algorithms and Computations. Lecture Notes in Computer Science Series, vol. 5942. Springer-Verlag, 21--34. Google ScholarDigital Library
- Ghosh, S. K., Maheshwari, A., Pal, S. P., Saluja, S., and Veni Madhavan, C. E. 1993. Characterizing and recognizing weak visibility polygons. Comput. Geom. Theory Appl. 3, 213--233. Google ScholarDigital Library
- Ghosh, S. K. and Mount, D. M. 1991. An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20, 888--910. Google ScholarDigital Library
- Ghosh, S. K. and Roy, B. 2012a. Some results on point visibility graphs. CoRR abs/1209.2308.Google Scholar
- Ghosh, S. K. and Roy, B. 2012b. Two necessary conditions for recognizing point visibility graphs. Manuscript, Tata Institute of Fundamental Research. May.Google Scholar
- Ghosh, S. K., Shermer, T., Bhattacharya, B. K., and Goswami, P. P. 2007. Computing the maximum clique in the visibility graph of a simple polygon. J. Discrete Algorithms 5, 524--532. Google ScholarDigital Library
- Gilbers, A. and Klein, R. 2011. A new upper bound for the VC-dimension of visibility regions. In Proceedings of the 27th Annual ACM Symposium on Computational Geometry. 380--386. Google ScholarDigital Library
- Goodman, J. E. and Pollack, R. 1984. Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory A 37, 257--293.Google ScholarCross Ref
- Goodman, J. E. and Pollack, R. 1986. Upper bounds for configurations and polytopes in Rd. Discrete Comput. Geom. 1, 219--227.Google ScholarDigital Library
- Har-Peled, S. 2011. Geometric Approximation Algorithms. American Mathematical Society. Google ScholarDigital Library
- Harborth, H. 1978. Konvexe fnfecke in ebenen punktmengen. Elemente der Mathematik 33, 116--118.Google Scholar
- Hartke, S. G., Vandenbussche, J., and Wenger, P. 2007. Further results on bar k-visibility graphs. SIAM J. Discrete Math. 21, 523--531. Google ScholarDigital Library
- Hernández-Barrera, A., Hurtado, F., Urrutia, J., and Zamora, C. 2001. On the midpoints of a plane point set. Unpublished manuscript.Google Scholar
- Hershberger, J. 1989. Finding the visibility graph of a polygon in time proportional to its size. Algorithmica 4, 141--155.Google ScholarCross Ref
- Hoffmann, M. and Tóth, C. 2003. Alternating paths through disjoint line segments. Inf. Process. Lett. 87, 287--294. Google ScholarDigital Library
- Hoffmann, M. and Toth, C. 2003. Segment endpoint visibility graphs are hamiltonian. Comput. Geom. Theory Appl. 26, 47--68. Google ScholarDigital Library
- Horton, J. 1983. Sets with no empty 7-gons. Can. Math. Bull. 26, 482--484.Google ScholarCross Ref
- Jackson, L. and Wismath, S. K. 2002. Orthogonal polygon reconstruction from stabbing information. Comput. Geom. Theory Appl. 23, 69--83. Google ScholarDigital Library
- Kalai, G. and J. Matoušek, J. 1997. Guarding galleries where every point sees a large area. Israel J. Math. 101, 125--139.Google ScholarCross Ref
- Kára, J., Pór, A., and Wood, D. R. 2005. On the chromatic number of the visibility graph of a set of points in the plane. Discrete Comput. Geom. 34, 3, 497--506. Google ScholarDigital Library
- King, J. 2008. VC-dimension of visibility on terrains. In Proceedings of the 20th Canadian Conference on Computational Geometry. 27--30.Google Scholar
- King, J. and Kirkpatrick, D. G. 2011. Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46, 2, 252--269. Google ScholarDigital Library
- Kirkpatrick, D. and Wismath, S. 1996. Determining bar-representability for ordered weighted graphs. Comput. Geom. Theory Appl. 6, 99--122. Google ScholarDigital Library
- Knuth, D. E. 1992. Axioms and hulls. Lecture Notes in Computer Science Series, vol. 606. Springer-Verlag.Google Scholar
- Komlós, J., Pach, J., and Woeginger, G. 1992. Almost tight bounds for ε-nets. Discrete Comput. Geom. 7, 163--173.Google ScholarDigital Library
- Koshelev, V. 2007. On the Erdös-Szekeres problem in combinatorial geometry. Electron. Notes Discrete Math. 29, 175--177.Google ScholarCross Ref
- Lee, D. T. 1978. Proximity and Reachability in the Plane. Tech. rep. ACT-12 and Ph.D. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, IL. Google ScholarDigital Library
- Lee, D. T. and Lin, A. K. 1986. Computational complexity of art gallery problems. IEEE Trans. Inf. Theory IT--32, 2, 276--282. Google ScholarDigital Library
- Lin, S. Y. and Chen, C. Y. 1994. Planar visibility graphs. In Proceedings of the 6th Canadian Conference on Computational Geometry. 30--35.Google Scholar
- Lin, S. Y. and Skiena, S. 1995. Complexity aspects of visibility graphs. Int. J. Comput. Geom. Appl. 5, 289--312.Google ScholarCross Ref
- Lozano-Perez, T. and Wesley, M. A. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22, 560--570. Google ScholarDigital Library
- Luccio, F., Mazzone, S., and Wong, C. K. 1987. A note on visibility graphs. Discrete Math. 64, 209--219. Google ScholarDigital Library
- Matousek, J. 2002. Lecture on Discrete Geometry. Graduate Text in Mathematics Series, vol. 212. Springer. Google ScholarDigital Library
- Matousek, J. 2009. Blocking visibility for points in general position. Discrete Comput. Geom. 42, 219--223. Google ScholarDigital Library
- Mirzaian, A. 1992. Hamiltonian triangulations and circumscribing polygons of disjoint line segments. Comput. Geom. Theory Appl. 2, 15--30. Google ScholarDigital Library
- Morris, W. and Soltan, V. 2000. The Erdös-Szekeres problem on points in convex position—a survey. Bull. Am. Math. Soc. 37, 437--458.Google ScholarCross Ref
- Mukkamala, P., Pach, J., and Sariöz, D. 2010. Graphs with large obstacles numbers. In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science. Number 6410 in Lecture Notes in Computer Science. Springer-Verlag, 203--215. Google ScholarDigital Library
- Mutzel, P., Odenthal, T., and Scharbrodt, M. 1998. The thickness of graphs: A survey. Graphs Comb. 14, 59--73.Google ScholarCross Ref
- Mycielski, J. 1955. Sur le coloriage des graphes. Colloquim Math. 3, 161--162.Google Scholar
- Nicolás, C. M. 2007. The empty hexagon theorem. Discrete Comput. Geom. 38, 389--397. Google ScholarDigital Library
- O'Rourke, J. 1987. Art Gallery Theorems and Algorithms. Oxford University Press, New York. Google ScholarDigital Library
- O'Rourke, J. 1998. Open problems in the combinatorics of visibility and illumination. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, Eds. (Contemporary Mathematics) American Mathematical Society, 237--243.Google Scholar
- O'Rourke, J. and Rippel, J. 1994. Two segment classes with Hamiltonian visibility graphs. Comput. Geom. Theory Appl. 4, 209--218. Google ScholarDigital Library
- O'Rourke, J. and Streinu, I. 1997. Vertex-edge pseudo-visibility graphs: characterization and recognition. In Proceedings of the 13th Annual ACM Symposium on Computational Geometry. 119--128. Google ScholarDigital Library
- Overmars, M. H. 2003. Finding sets of points without empty convex 6-gons. Discrete Comput. Geom. 29, 153--158.Google ScholarCross Ref
- Pach, J. 2003. Midpoints of segments induced by a point set. Geombinatorics 13, 98--105.Google Scholar
- Payne, M. S., Pór, A., Valtr, P., and Wood, D. R. 2011. On the connectivity of visibility graphs. ArXive e-prints arXiv:1106.3622.Google Scholar
- Payne, M. S., Pór, A., Valtr, P., and Wood, D. R. 2012. On the connectivity of visibility graphs. Discrete Comput. Geom. 48, 3, 669--681. Google ScholarDigital Library
- Pfender, F. 2008. Visibility graphs of point sets in the plane. Discrete Comput. Geom. 39, 1, 455--459. Google ScholarDigital Library
- Plesník, J. 1975. Critical graphs of given diameter. Acta Fac. Rerum Natur. Univ. Comenian. Math. 30, 71--93.Google Scholar
- Pocchiola, M. and Vegter, G. 1996. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comput. Geom. 16, 419--453.Google ScholarDigital Library
- Pór, A. and Wood, D. R. 2010. On visibility and blockers. J. Comput. Geom. 1, 29--40.Google Scholar
- Ramsey, F. P. 1930. On a problem of formal logic. In Proceedings of the London Mathematical Society, Series 2 30, 264--286.Google Scholar
- Rappaport, D. 1989. Computing simple circuits from a set of line segments is NP-complete. SIAM J. Comput. 18, 1128--1139. Google ScholarDigital Library
- Rappaport, D., Imai, H., and Toussaint, G. T. 1990. Computing simple circuits from a set of line segments. Discrete Comput. Geom. 5, 289--304.Google ScholarDigital Library
- Raz, R. and Safra, S. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing. 475--484. Google ScholarDigital Library
- Romanlk, K. 1997. Directed rectangle-visibility graphs have unbounded dimension. Discrete Appl. Math. 73, 35--39.Google ScholarCross Ref
- Rosenstiehl, P. and Tarjan, R. E. 1986. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343--353.Google ScholarDigital Library
- Roy, B. May 2011. Recognizing point visibility graphs. Graduate School Project Report, Tata Institute of Fundamental Research.Google Scholar
- Schlag, M., Luccio, F., Maestrini, P., Lee, D. T., and Wong, C. 1985. A visibility problem in VLSI layout compaction. In Advances in Computing Research, F. Preparata, Ed., JAI Press Inc., 259--282.Google Scholar
- Shapiro, L. G. and Haralick, R. M. 1979. Decomposition of two-dimensional shape by graph-theoretic clustering. IEEE Trans. Pattern Anal. Mach. Intell. 1, 10--19. Google ScholarDigital Library
- Sharir, M. and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 193--215. Google ScholarDigital Library
- Shermer, T. 1989. Hiding people in polygons. Computing 42, 109--131. Google ScholarDigital Library
- Shermer, T. 1992. Recent results in art galleries. Proc. IEEE 80, 1384--1399.Google ScholarCross Ref
- Shermer, T. 1996. On rectangle visibility graphs, III: External visibility and complexity. In Proceedings of the 8th Canadian Conference on Computational Geometry. 234--239. Google ScholarDigital Library
- Spinrad, J. P. 2003. Efficient Graph Representations. American Mathematical Society.Google Scholar
- Srinivasaraghavan, G. and Mukhopadhyay, A. 1994. A new necessary condition for the vertex visibility graphs of simple polygons. Discrete Comput. Geom. 12, 65--82.Google ScholarDigital Library
- Stanchescu, Y. V. 2002. Planar sets containing no three collinear points and non-averaging sets of integers. Discrete Math. 256, 387--395. Google ScholarDigital Library
- Streinu, I. 1999. Non-stretchable pseudo-visibility graphs. In Proceedings of the 11th Canadian Conference on Computational Geometry. 22--25.Google Scholar
- Streinu, I. 2005. Non-stretchable pseudo-visibility graphs. Comput. Geom. Theory Appl. 31, 195--206. Google ScholarDigital Library
- Streinu, I. and Whitesides, S. 2003. Rectangle visibility graphs: characterization, construction, and compaction. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes of Computer Science Series, vol. 2607. Springer-Verlag, 26--37. Google ScholarDigital Library
- Suri, S., Vicari, E., and Widmayer, P. 2008. Simple robots with minimal sensing: From local visibility to global geometry. Int. J. Robotic Res. 27, 1055--1067. Google ScholarDigital Library
- Tamassia, R. and Tollis, I. 1986. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 321--341.Google ScholarDigital Library
- Tóth, G. and Valtr, P. 2005. The Erdös-Szekeres theorem: upper bounds and related results. In Combinatorial and Computational Geometry, J. E. Goodman, J. Pach, and E. Welzl, Eds., vol. 52. Cambridge University Press, Cambridge, 557--568.Google Scholar
- Urabe, M. and Watanabe, M. 1992. On a counterexample to a conjecture of Mirzaian. Comput. Geom. Theory Appl. 2, 51--53. Google ScholarDigital Library
- Urrutia, J. 2000. Art gallery and illumination problems. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds., North-Holland, 973--1023.Google Scholar
- Urrutia, J. 2002. Open problems in computational geometry. In Proceedings of the 5th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science Series, vol. 2286. Springer-Verlag, 4--11. Google ScholarDigital Library
- Valtr, P. 1998. Guarding galleries where no point sees a small area. Israel J. Math. 104, 1--16.Google ScholarCross Ref
- Vapnik, V. N. and Chervonenkis, A. Y. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications 16, 264--280.Google ScholarCross Ref
- Warren, H. 1968. Lower bounds for approximation by nonlinear manifolds. Trans. AMS 133, 167--178.Google ScholarCross Ref
- Welzl, E. 1985. Constructing the visibility graph for n line segments in O(n2) time. Inf. Process. Lett. 20, 167--171.Google ScholarCross Ref
- Wismath, S. K. 1985. Characterizing bar line-of-sight graphs. In Proceedings of the 1st ACM Symposium on Computational Geometry. 147--152. Google ScholarDigital Library
Index Terms
- Unsolved problems in visibility graphs of points, segments, and polygons
Recommendations
Reducing Hajós' 4-coloring conjecture to 4-connected graphs
Hajós conjectured that, for any positive integer k, every graph containing no Kk+1-subdivision is k-colorable. This is true when k ≤ 3, and false when k ≥ 6. Hajós' conjecture remains open for k = 4, 5. In this paper, we show that any possible ...
Mapping Simple Polygons: The Power of Telling Convex from Reflex
We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that ...
On H-Topological Intersection Graphs
AbstractBiró et al. (Discrete. Math 100(1–3):267–279, 1992) introduced the concept of H-graphs, intersection graphs of connected subgraphs of a subdivision of a graph H. They are related to and generalize many important classes of geometric intersection ...
Comments