On recognizing and characterizing visibility graphs of simple polygons

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