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

Chiuyuan Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Two vertices of a simple polygon P are visible if the line segment joining them does not intersect the exterior of P. The visibility 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.

Original languageEnglish
Pages (from-to)417-424
Number of pages8
JournalTheoretical Computer Science
Volume276
Issue number1-2
DOIs
StatePublished - 6 Apr 2002

Keywords

  • Computational geometry
  • Polygon
  • Visibility graph
  • Visibility problem

Fingerprint Dive into the research topics of 'A necessary condition for a graph to be the visibility graph of a simple polygon'. Together they form a unique fingerprint.

  • Cite this