Disproving a conjecture on planar visibility graphs

Chiuyuan Chen*, Kaiping Wu

*Corresponding author for this work

研究成果: Article同行評審


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.

頁(從 - 到)659-665
期刊Theoretical Computer Science
出版狀態Published - 7 八月 2001

指紋 深入研究「Disproving a conjecture on planar visibility graphs」主題。共同形成了獨特的指紋。