Abstract
Two vertices A and B of a simple polygon P are (mutually) visible if AB does not intersect the exterior of P. A graph G is a visibility graph if there exists a simple polygon P such that each vertex of G corresponds to a vertex of P and two vertices of G are joined by an edge if and only if their corresponding vertices in P are visible. No characterization of visibility graphs is available. Abello, Lin and Pisupati conjectured that every hamiltonian maximal planar graph with a 3-clique ordering is a visibility graph. In this paper, we disprove this conjecture.
Original language | English |
---|---|
Pages (from-to) | 659-665 |
Number of pages | 7 |
Journal | Theoretical Computer Science |
Volume | 255 |
Issue number | 1-2 |
DOIs | |
State | Published - 7 Aug 2001 |
Keywords
- Computational geometry
- Hamiltonian cycle
- Planar graph
- Visibility graph
- Visibility problem