Abstract:
A plane graph is a planar graph with a fixed embedding in the plane. In a
box- rectangular drawing of a plane graph, every vertex is drawn as a rectangle,
called a box, each edge is drawn as either a horizontal line segment or a vertical
line segment, and the contour of each face is drawn as a rectangle. A planar
graph is said to have a box-rectangular drawing if at least one of its plane
embeddings has a box-rectangular drawing. In this thesis we give a linear-time
algorithm to examine whether a planar graph G has a box-rectangular drawing
or not, and to find a box-rectangular drawing of G if it exists. We first give an
algorithm for box-rectangular drawings of planar graphs of the maximum degree
three. We then reduce the problem of box-rectangular drawings of planar graphs
of the maximum degree four or more to the problem of box-rectangular drawings
of planar graphs of the maximum degree three.
ix
