6.1 Introduction

A rectangular drawing of a plane graph G is a drawing of G in which each vertex is drawn as a point, each edge is drawn as a horizontal or vertical line segment without edge-crossings, and each face is drawn as a rectangle. Thus a rectangular drawing is a special case of a convex drawing. Figure 6.1(b) illustrates a rectangular drawing of the plane graph in Fig. 6.1(a). In Section 1.5.1 we have seen applications of a rectangular drawing to VLSI floorplanning and architectural floorplanning. In a rectangular drawing of G, the outer cycle C _o( G) is drawn as a rectangle and hence has four convex corners such as a, b, c and d drawn by white circles in Fig. 6.1. Such a convex corner is an outer vertex of degree two and is called a corner of the rectangular drawing. Not every plane graph G has a rectangular drawing. Of course, G must be 2-connected and the maximum degree ? of G is at most four if G has a rectangular drawing.

Fig. 6.1: (a) Plane graph, and (b) its rectangular drawing for the designated corners a, b, c and d.

Miura et al. recently showed that a plane graph G with ? ?4 has rectangular drawing D if and only if a new bipartite graph constructed from G has a perfect matching, and D