Distance visibility graphs
- 1 January 1991
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2 (4) , 289-296
- https://doi.org/10.1145/109648.109681
Abstract
A new necessary condition for a graph G to be the visibility graph of a simple polygon is given: each 3connected component of G must. have a vertex ordering in which every vertex is adjacent to a previous 3-clique. This property is used to give an algorithm for the distance visibility graph problem: given an edge-weighted graph G, is it the visibility graph of a simple polygon with the given weights as Euclidean distances?Keywords
This publication has 0 references indexed in Scilit: