Return to search

Structural properties of visibility and weak visibility graphs

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

Identiferoai:union.ndltd.org:BSU/oai:cardinalscholar.bsu.edu:handle/185812
Date January 1997
CreatorsDey, Sanjoy
ContributorsBall State University. Dept. of Mathematical Sciences., Bagga, Kunwarjay S.
Source SetsBall State University
Detected LanguageEnglish
Formatvii, 62 leaves : ill. ; 28 cm.
SourceVirtual Press

Page generated in 0.0019 seconds