ON RECOGNIZING AND CHARACTERIZING VISIBILITY GRAPHS OF SIMPLE POLYGONS

Authors
GHOSH SK
Citation
Sk. Ghosh, ON RECOGNIZING AND CHARACTERIZING VISIBILITY GRAPHS OF SIMPLE POLYGONS, Discrete & computational geometry, 17(2), 1997, pp. 143-162
Citations number
22
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
17
Issue
2
Year of publication
1997
Pages
143 - 162
Database
ISI
SICI code
0179-5376(1997)17:2<143:ORACVG>2.0.ZU;2-0
Abstract
In this paper we establish four necessary conditions for recognizing v isibility graphs of simple polygons and conjecture that these conditio ns are sufficient. We present an O(n(2))-time algorithm for testing th e first and second necessary conditions and leave it open whether the third and fourth necessary conditions can be tested in polynomial time . We also show that visibility graphs of simple polygons do not posses s the characteristics of a few special classes of graphs.