Disproving a conjecture on planar visibility graphs

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. (C) 2001 Elsevier Science B.V. All rights reserved.