Disproving a conjecture on planar visibility graphs

Chiuyuan Chen*, Kaiping Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)659-665
Number of pages7
JournalTheoretical Computer Science
Volume255
Issue number1-2
DOIs
StatePublished - 7 Aug 2001

Keywords

  • Computational geometry
  • Hamiltonian cycle
  • Planar graph
  • Visibility graph
  • Visibility problem

Fingerprint Dive into the research topics of 'Disproving a conjecture on planar visibility graphs'. Together they form a unique fingerprint.

Cite this