Disproving a conjecture on planar visibility graphs
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
665 | en_US |
dc.citation.issue |
1-2 | en_US |
dc.citation.spage |
659 | en_US |
dc.citation.volume |
255 | en_US |
dc.citation.woscount |
3 | |
dc.contributor.author |
Chen, CY | en_US |
dc.contributor.author |
Wu, KP | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:44:02Z | |
dc.date.available |
2014-12-08T15:44:02Z | |
dc.date.issued |
2001-03-28 | en_US |
dc.description.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. (C) 2001 Elsevier Science B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/S0304-3975(00)00391-1 | en_US |
dc.identifier.issn |
0304-3975 | en_US |
dc.identifier.journal |
THEORETICAL COMPUTER SCIENCE | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/S0304-3975(00)00391-1 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/29761 | |
dc.identifier.wosnumber |
WOS:000167792100037 | |
dc.language.iso |
en_US | en_US |
dc.subject |
computational geometry | en_US |
dc.subject |
visibility problem | en_US |
dc.subject |
visibility graph | en_US |
dc.subject |
planar graph | en_US |
dc.subject |
Hamiltonian cycle | en_US |
dc.title |
Disproving a conjecture on planar visibility graphs | en_US |
dc.type |
Article | en_US |
檔案
- 000167792100037.pdf (127.0 KB, Adobe PDF)
所屬典藏: 期刊論文