Disproving a conjecture on planar visibility graphs
檔案
- 000167792100037.pdf (127.0 KB, Adobe PDF)
日期
2001-03-28
類型
系所
期刊名稱
THEORETICAL COMPUTER SCIENCE
卷期與頁次
第 255 卷第 1-2 期,頁 659–665
ISSN
0304-3975
語言
英文
摘要
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.