完整後設資料紀錄
DC 欄位語言
dc.contributor.authorChen, CYen_US
dc.date.accessioned2014-12-08T15:42:31Z-
dc.date.available2014-12-08T15:42:31Z-
dc.date.issued2002-04-06en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://dx.doi.org/10.1016/S0304-3975(01)00208-0en_US
dc.identifier.urihttp://hdl.handle.net/11536/28869-
dc.description.abstractTwo vertices of a simple polygon P are visible if the line segment joining them does not intersect the exterior of P. The visibilitly graph of P is a graph G obtained by representing each vertex of P by a vertex of G and two vertices of G are joined by an edge if and only if their corresponding vertices in P are visible. A graph G is a visibility graph if there exists a simple polygon P such that G is isomorphic to the visibility graph of P. No characterization of visibility graphs is available. Coullard and Lubiw derived a necessary condition for a graph to be the visibility graph of a simple polygon. They proved that any 3-connected component of a visibility graph has a 3-clique ordering starting from any triangle. However, Coullard and Lubiw insisted on the non-standard definition of visibility (the line segment joining two visible vertices may not go through intermediate vertices) and they said they do not know if their result will hold under the standard definition of visibility. The purpose of this paper is to prove that Coullard and Lubiw's result still holds under the standard definition of visibility. (C) 2002 Elsevier Science B.V. All rights reserved.en_US
dc.language.isoen_USen_US
dc.subjectcomputational geometryen_US
dc.subjectvisibility problemen_US
dc.subjectvisibility graphen_US
dc.subjectpolygonen_US
dc.titleA necessary condition for a graph to be the visibility graph of a simple polygonen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/S0304-3975(01)00208-0en_US
dc.identifier.journalTHEORETICAL COMPUTER SCIENCEen_US
dc.citation.volume276en_US
dc.citation.issue1-2en_US
dc.citation.spage417en_US
dc.citation.epage424en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000175420800019-
dc.citation.woscount3-
顯示於類別:期刊論文


文件中的檔案:

  1. 000175420800019.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。