Full metadata record
DC FieldValueLanguage
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-
Appears in Collections:Articles


Files in This Item:

  1. 000175420800019.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.