Structural properties of visibility and weak visibility graphs

Cardinal Scholar

Show simple item record

dc.contributor.advisor Bagga, Jay en_US Dey, Sanjoy en_US 2011-06-03T19:37:46Z 2011-06-03T19:37:46Z 1997 en_US 1997
dc.identifier LD2489.Z78 1997 .D49 en_US
dc.description.abstract 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.
dc.description.sponsorship Department of Mathematical Sciences
dc.format.extent vii, 62 leaves : ill. ; 28 cm. en_US
dc.source Virtual Press en_US
dc.subject.lcsh Graphic methods. en_US
dc.subject.lcsh Hamiltonian graph theory. en_US
dc.subject.lcsh Graph theory. en_US
dc.title Structural properties of visibility and weak visibility graphs en_US Thesis (M.S.)
dc.identifier.cardcat-url en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

  • Master's Theses [5510]
    Master's theses submitted to the Graduate School by Ball State University master's degree candidates in partial fulfillment of degree requirements.

Show simple item record

Search Cardinal Scholar


My Account