Box - rectangular drawings of planar graphs

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