|標題:||Disproving a conjecture on planar visibility graphs|
Department of Applied Mathematics
|關鍵字:||computational geometry;visibility problem;visibility graph;planar graph;Hamiltonian cycle|
|摘要:||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.|
|期刊:||THEORETICAL COMPUTER SCIENCE|
|Appears in Collections:||Articles|
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.