標題: Disproving a conjecture on planar visibility graphs
作者: Chen, CY
Wu, KP
應用數學系
Department of Applied Mathematics
關鍵字: computational geometry;visibility problem;visibility graph;planar graph;Hamiltonian cycle
公開日期: 28-Mar-2001
摘要: 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.
URI: http://dx.doi.org/10.1016/S0304-3975(00)00391-1
http://hdl.handle.net/11536/29761
ISSN: 0304-3975
DOI: 10.1016/S0304-3975(00)00391-1
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 255
Issue: 1-2
起始頁: 659
結束頁: 665
Appears in Collections:Articles


Files in This Item:

  1. 000167792100037.pdf