Given a finite set S of n nonintersecting line segments with no three end points collinear, the segment end point visibility graph is defined as the graph whose vertices are the end points of the line segments in S and two vertices are adjacent if the straight line segment joining two end points does not intersect any element of S, or if they are end points of the same segment. Segment end point visibility graphs have a wide variety of applications in VLSI circuit design, study of art gallery problems, and other areas of computational geometry. This thesis contains a survey of the important results that are currently known regarding the characterization of these graphs. Also a weak visibility dual of a segment end point visibility graph is defined and some structural properties of such graphs are presented. Some open problems and questions related to the characterization of weak visibility graphs are also discussed. / Department of Mathematical Sciences
| Identifer | oai:union.ndltd.org:BSU/oai:cardinalscholar.bsu.edu:handle/185812 |
| Date | January 1997 |
| Creators | Dey, Sanjoy |
| Contributors | Ball State University. Dept. of Mathematical Sciences., Bagga, Kunwarjay S. |
| Source Sets | Ball State University |
| Detected Language | English |
| Format | vii, 62 leaves : ill. ; 28 cm. |
| Source | Virtual Press |
Page generated in 0.0023 seconds