A necessary condition for a graph to be the visibility graph of a simple polygon

Abstract

Two vertices of a simple polygon P are visible if the line segment joining them does not intersect the exterior of P. The visibilitly graph of P is a graph G obtained by representing each vertex of P by a vertex of G and two vertices of G are joined by an edge if and only if their corresponding vertices in P are visible. A graph G is a visibility graph if there exists a simple polygon P such that G is isomorphic to the visibility graph of P. No characterization of visibility graphs is available. Coullard and Lubiw derived a necessary condition for a graph to be the visibility graph of a simple polygon. They proved that any 3-connected component of a visibility graph has a 3-clique ordering starting from any triangle. However, Coullard and Lubiw insisted on the non-standard definition of visibility (the line segment joining two visible vertices may not go through intermediate vertices) and they said they do not know if their result will hold under the standard definition of visibility. The purpose of this paper is to prove that Coullard and Lubiw's result still holds under the standard definition of visibility. (C) 2002 Elsevier Science B.V. All rights reserved.