Ghosh, S. K. (1997) On recognizing and characterizing visibility graphs of simple polygons Discrete & Computational Geometry, 17 (2). pp. 143-162. ISSN 0179-5376
Full text not available from this repository.
Official URL: http://www.springerlink.com/content/heylug6r6c3f8g...
Related URL: http://dx.doi.org/10.1007/BF02770871
Abstract
In this paper we establish four necessary conditions for recognizing visibility graphs of simple polygons and conjecture that these conditions are sufficient. We present an O(n2)-time algorithm for testing the 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 possess the characteristics of a few special classes of graphs.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer. |
| ID Code: | 76277 |
| Deposited On: | 31 Dec 2011 08:56 |
| Last Modified: | 31 Dec 2011 08:56 |
Repository Staff Only: item control page
