- ACP.S. Arnborg, D.G. Corneil, A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic and Discrete Methods 8, 1987, 277-284. Google ScholarDigital Library
- AP.S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, SIAM J. Algebraic and Discrete Methods 7, 1986, 305- 314. Google ScholarDigital Library
- CM.L. Cat and F. Maffray, private communication, 1990.Google Scholar
- Ch.B. Chazelle, to appear in Proc. 31st IEEE Symp. on Foundations of Computing, 1990.Google Scholar
- EC.H. Everett and D. Corneil, Recognizing visibility graphs of spiral polygons, J. of Algorithms 11, 1990, 1-26. Google ScholarDigital Library
- E-G.H. El-Cindy, Hierarchical Decomposition of Polygons with Applications, Ph.D. Thesis, Mc- Gill University, Montreal, Quebec, 1985. Google ScholarDigital Library
- Gh.S.K. Ghosh, On recognizing and characterizing visibility graphs of simple polygons, Lecture Notes in Computer Science 318, Springer- Verlag, 1988. Google ScholarDigital Library
- H.J. Hershberger, Finding the visilbility graph of a simple polygon in time proportional to its size, Proc. 3rd ACM Symp. on Computational Geometry, 1987, 11-20. Google ScholarDigital Library
- HT.J. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Computing 2, 1973, 135-158.Google Scholar
- O'R.J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Piess, 1987. Google ScholarDigital Library
- O'R2.J. O'Rourke, Recovery of convexity from visibility graphs, manuscript, 1990.Google Scholar
- PS.F.P. Preparata and M.I. Shamos, Computational Geomefry: an Introduction, Springer- Verlag, 1985. Google ScholarDigital Library
- OW.M.H. Overmars and E. Welzl, New methods for computing visibility graphs, Proc. 4th ACM Symp. on Computational Geometry, 1988, 164- 171. Google ScholarDigital Library
- RS.N. Robertson and P.D. Seymour, Graph minors II. Algorithmic aspects of tree width, J. of Algorithms 7, 1986, 309-322.Google Scholar
- Sa.J.B. Saxe, Two papers on graph embedding problems, Technical Report CMU-CS-80-102, Dept. of Computer Science, Carnegie Mellon University, 1980.Google Scholar
- To.P. Todd, A k-tree generalization that characterizes consistency of dimensioned engineering drawings, SIAM J. Discrete Math. 2, 1989, 255- 261. Google ScholarDigital Library
- TY.R.E. Tarjan and M. Yannakakis, Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Computing 13, 1984, 566-579. Google ScholarDigital Library
- Ya.M. Yannakakis, Edge deletion problems, SIAM J. Computing 10, 1981, 297-309.Google ScholarCross Ref
- Ye.Y. Yemeni, On some theoretical aspects of position-location problems, Proc. 10th IEEE Symp. on Foundations of Computer Science, 1979, 1-8.Google ScholarDigital Library
Index Terms
- Distance visibility graphs
Recommendations
Spanners for Geodesic Graphs and Visibility Graphs
Let $$\mathcal{P}$$P be a set of n points inside a polygonal domain $$\mathcal{D}$$D. A polygonal domain with h holes (or obstacles) consists of h disjoint polygonal obstacles surrounded by a simple polygon which itself acts as an obstacle. We first ...
Can visibility graphs be represented compactly?
SCG '93: Proceedings of the ninth annual symposium on Computational geometryWe consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G={G1,G2,...,Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii)...
Colouring exact distance graphs of chordal graphs
AbstractFor a graph G = ( V , E ) and positive integer p, the exact distance- p graph G [ ♮ p ] is the graph with vertex set V and with an edge between vertices x and y if and only if x and y have distance p. ...
Comments