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.

Digital Library

Google Scholar

[9]

J. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Computing 2, 1973, 135-158.

Google Scholar

[10]

J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Piess, 1987.

Digital Library

Google Scholar

[11]

J. O'Rourke, Recovery of convexity from visibility graphs, manuscript, 1990.

Google Scholar

[12]

F.P. Preparata and M.I. Shamos, Computational Geomefry: an Introduction, Springer- Verlag, 1985.

Digital Library

Google Scholar

[13]

M.H. Overmars and E. Welzl, New methods for computing visibility graphs, Proc. 4th ACM Symp. on Computational Geometry, 1988, 164- 171.

Digital Library

Google Scholar

[14]

N. Robertson and P.D. Seymour, Graph minors II. Algorithmic aspects of tree width, J. of Algorithms 7, 1986, 309-322.

Google Scholar

[15]

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

[16]

P. Todd, A k-tree generalization that characterizes consistency of dimensioned engineering drawings, SIAM J. Discrete Math. 2, 1989, 255- 261.

Digital Library

Google Scholar

[17]

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.

Digital Library

Google Scholar

[18]

M. Yannakakis, Edge deletion problems, SIAM J. Computing 10, 1981, 297-309.

Crossref

Google Scholar

[19]

Y. Yemeni, On some theoretical aspects of position-location problems, Proc. 10th IEEE Symp. on Foundations of Computer Science, 1979, 1-8.

Digital Library

Google Scholar

Cited By

View all

Chalopin JDas SDisser YMihaláK MWidmayer P(2013)PerspectiveDiscrete Applied Mathematics10.1016/j.dam.2013.01.006161:10-11(1287-1307)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.dam.2013.01.006
Disser YMihalák MWidmayer P(2013)Mapping Polygons with Agents That Measure AnglesAlgorithmic Foundations of Robotics X10.1007/978-3-642-36279-8_25(415-425)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36279-8_25
Dehghani GMorady H(2009)An Algorithm for Visibility Graph Recognition on Planar GraphsProceedings of the 2009 International Conference on Future Computer and Communication10.1109/ICFCC.2009.97(518-521)Online publication date: 3-Apr-2009
https://dl.acm.org/doi/10.1109/ICFCC.2009.97
Show More Cited By

Index Terms

Distance visibility graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

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 geometry

We 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={G₁,G₂,...,G_k} 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
Abstract
For 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

Information & Contributors

Information

Published In

SCG '91: Proceedings of the seventh annual symposium on Computational geometry

June 1991

373 pages

ISBN:0897914260

DOI:10.1145/109648

Chairman:
R. L. Scot Drysdale

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOCG91

Sponsor:

SOCG91: 7th Annual Symposium on Computational Geometry 1991

June 10 - 12, 1991

New Hampshire, North Conway, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
570
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)3

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chalopin JDas SDisser YMihaláK MWidmayer P(2013)PerspectiveDiscrete Applied Mathematics10.1016/j.dam.2013.01.006161:10-11(1287-1307)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.dam.2013.01.006
Disser YMihalák MWidmayer P(2013)Mapping Polygons with Agents That Measure AnglesAlgorithmic Foundations of Robotics X10.1007/978-3-642-36279-8_25(415-425)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36279-8_25
Dehghani GMorady H(2009)An Algorithm for Visibility Graph Recognition on Planar GraphsProceedings of the 2009 International Conference on Future Computer and Communication10.1109/ICFCC.2009.97(518-521)Online publication date: 3-Apr-2009
https://dl.acm.org/doi/10.1109/ICFCC.2009.97
Dehghani GMorady H(2009)An Algorithm for Visibility Graph Recognition on Special CaseProceedings of the 2009 International Conference on Future Computer and Communication10.1109/ICFCC.2009.131(209-211)Online publication date: 3-Apr-2009
https://dl.acm.org/doi/10.1109/ICFCC.2009.131
Morady HDehghani G(2009)An Algorithm for Visibility Graph Recognition on Simple CaseProceedings of the 2009 International Conference on Future Computer and Communication10.1109/ICFCC.2009.130(206-208)Online publication date: 3-Apr-2009
https://dl.acm.org/doi/10.1109/ICFCC.2009.130
Abello JKumar K(2005)Visibility graphs and oriented matroids (extended abstract)Graph Drawing10.1007/3-540-58950-3_366(147-158)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-58950-3_366
Choi SShin SChwa K(2005)Characterizing and recognizing visibility graphs of Funnel-shaped polygonsAlgorithms and Computation10.1007/3-540-56279-6_75(219-228)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-56279-6_75
Veach MKoza J(1996)Recognition and reconstruction of visibility graphs using a genetic algorithmProceedings of the 1st annual conference on genetic programming10.5555/1595536.1595622(491-496)Online publication date: 28-Jul-1996
https://dl.acm.org/doi/10.5555/1595536.1595622
Abello JEgecioglu OKumar K(1995)Visibility graphs of staircase polygons and the weak Bruhat order, IDiscrete & Computational Geometry10.1007/BF0257071014:3(331-358)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.1007/BF02570710
Choi SShin SChwa K(1995)Characterizing and recognizing the visibility graph of a funnel-shaped polygonAlgorithmica10.1007/BF0130037214:1(27-51)Online publication date: 1-Jul-1995
https://dl.acm.org/doi/10.1007/BF01300372
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Spanners for Geodesic Graphs and Visibility Graphs

Can visibility graphs be represented compactly?

Colouring exact distance graphs of chordal graphs

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Spanners for Geodesic Graphs and Visibility Graphs

Can visibility graphs be represented compactly?

Colouring exact distance graphs of chordal graphs

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations