TABLE OF CONTENTS A box-rectangular drawing of a plane graph G is a drawing of G such that each vertex is drawn as a rectangle, called a box, and the contour of each face is drawn as a rectangle, as illustrated in Fig. 1.6(d). A vertex may be drawn as a degenerate rectangle, that is, a point. We have seen in Section 1.5.1 that box-rectangular drawings have practical applications in floorplanning of MultiChip Modules (MCM) and in architectural floorplanning. If G has multiple edges or a vertex of degree five or more, then G has no rectangular drawing but may have a box-rectangular drawing. However, not every plane graph has a box-rectangular drawing. Rahman et al. [RNN00] established a necessary and sufficient condition for the existence of a box-rectangular drawing of a plane graph, and gave a linear algorithm to find a box-rectangular drawing if it exists.
In this chapter we present the results of Rahman et al. In Section 7.2 we presents some definitions and observations regarding box-rectangular drawings. In Section 7.3 we present a linear algorithm to find a box-rectangular drawing for a case where four outer vertices are designated as the corner boxes of the drawing. In Section 7.4 we present a linear algorithm to find a box-rectangular drawing for a general case in which no vertices are designated as the corner boxes.
In this section we give some definitions and preliminary observations regarding box-rectangular drawings.
Throughout this...
