Computational geometry column 18

ABSTRACT

Results on visibility graphs are classified and organized into five tables.

REFERENCES

• 1: [AEK92a] J. Abello, O. Egecioglu, and K. Kumar, Visibility graphs of staircase polygons and the weak Bruhat order I: from visibility graphs to maximal chains. Discrete and Computational Geometry, 1992. To appear.
• 2: [AEK92b] J. Abello, O. Egecioglu, and K. Kumar. Visibility graphs of staircase polygons and the weak Bruhat order II: from maximal chains to polygons. Discrete and Computational Geometry, 1992. To appear.
• 3: [ALP92] J. Abello, H. Lin, and S. Pisupati. On visibility graphs of simple polygons. Congresuss Numerantium Journal, 1992. To appear.
• 4: [And89] T. Andreae. Some results on visibility graphs, 1989. Preprint.
• 5: Collette Coullard , Anna Lubiw, Distance visibility graphs, Proceedings of the seventh annual symposium on Computational geometry, p.289-296, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109681]
• 6: [Col92] P. Colley. Recognizing visibility graphs of uni-monotone polygons. In Proc. 4th Canad. Conf. Comput. Geom., pages 29-34, St. John's, Newfoundland, 1992.
• 7: [EC90a] H. Everett and D. Corneil. Fobidden induced subgraphs of visibility graphs. Quoted in [She9O], 1990.
• 8: H. Everett , D. G. Corneil, Recognizing visibility graphs of spiral polygons, Journal of Algorithms, v.11 n.1, p.1-26, Mar. 1990 [doi>10.1016/0196-6774(90)90026-B]
• 9: Hossam Ahmed Elgindy, Hierarchical decomposition of polygons with applications, McGill University, Montreal, Que., Canada, 1985
• 10: [ELO91] H. Everett, A. Lubiw, and J. O'Rourke. Recovery of convex hulls from external visibility graphs. Smith College, 1991.
• 11: Hazel Jane Margaret Everett , D. G. Corneil, Visibility graph recognition, 1990
• 12: Subir Kumar Ghosh, On recognizing and characterizing visibility graphs of simple polygons, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.96-104, January 1988, Halmstad, Sweden
• 13: J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73046]
• 14: F. Luccio , S. Mazzone , C. K. Wong, A note on visibility graphs, Discrete Mathematics, v.64 n.2-3, p.209-219, April 1987 [doi>10.1016/0012-365X(87)90190-7]
• 15: [LS92] Y.-L. Lin and S. S. Skiena. Complexity aspects of visibility graphs. Technical Report 92/08, SUNY Stony Brook, Computer Science, 1992.
• 16: [Mir92] A. Mirzaian. Hamiltonian triangulations and circumscribing polygons of disjoint line segments. Computational Geometry: Theory and Applications, 1992. To appear. First presented in 1990 at the Canadian Computational Geometry Conference.
• 17: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 18: [O'R90] J. O'Rourke. Recovery of convexity from visibility graphs. Technical Report 90.4.6, Smith College, 1990.
• 19: [OR91] J. O'Rourke and J. Rippel. A class of segments whose visibility graphs are Hamiltonian. Technical Report 12, Smith College, 1991.
• 20: [OR92a] J. O'Rourke and J. Rippel. Segment visibility graphs: several results. In Proc. 4th Canad. Conf. Comput. Geom., pages 35-38, St. John's, Newfoundland, 1992.
• 21: [OR92b] J. O'Rourke and J. Rippel. Two segment classes with Hamiltonian visibility graphs. Technical Report 15, Smith College, 1992.
• 22: David Howard Rappaport, The complexity of computing simple circuits in the plane, 1987
• 23: D. Rappaport, Computing simple circuits from a set of line segments is NP-complete, SIAM Journal on Computing, v.18 n.6, p.1128-1139, Dec. 1989 [doi>10.1137/0218075]
• 24: David Rappaport , Hiroshi Imai , Godfried T. Toussaint, Computing simple circuits from a set of line segments, Discrete & Computational Geometry, v.5 n.3, p.289-304, May 1990 [doi>10.1007/BF02187791]
• 25: Xiaojun Shen , Herbert Edelsbrunner, A tight lower bound on the size of visibility graphs, Information Processing Letters, v.26 n.2, p.61-64, 19 Oct. 1987 [doi>10.1016/0020-0190(87)90038-X]
• 26: [She90] T. Shermer. Recent results in art galleries. Technical Report CMPT TR 90-10, Simon Fraser University, October 1990. To appear in IEEE Proceedings.
• 27: [SM91] G. Srivivasaraghavan and A. Mukhopadhyay. On some classes of unrealizable orthogonal visibility graphs. Indian Institute of Technology, 1991.
• 28: [Tho84] C. Thomassen. Plane representations of graphs. In Progress in Graph Theory, pages 43-69. Academic Press, 1984.
• 29: [TT86] R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1:321-341, 1986.
• 30: [Urr92] J. Urrutia, 1992. Personal communication at CCCG, August 1992.
• 31: Stephen K. Wismath, Characterizing bar line-of-sight graphs, Proceedings of the first annual symposium on Computational geometry, p.147-152, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323253]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory