Disproving a conjecture on planar visibility graphs

檔案

日期

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chen, C., & Wu, K. (2001). Disproving a conjecture on planar visibility graphs. THEORETICAL COMPUTER SCIENCE, 255(1-2), 659–665. https://doi.org/10.1016/S0304-3975(00)00391-1

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/29761