9.1 Introduction

In Chapters 6 and 8 we have studied rectangular drawings and orthogonal drawings of plane graphs, respectively. In this chapter we study an octagonal drawing which is an extension of a rectangular drawing and is a special type of an orthogonal drawing. An orthogonal drawing D of a plane graph G is called an octagonal drawing (with prescribed face areas) if (i) the outer cycle of D is a rectangle, (ii) each inner face has at most eight corners, and (iii) the area of each inner face is equal to a prescribed number. Figure 9.1(b) illustrates an octagonal drawing of the plane graph in Fig. 9.1(a), where a prescribed number is written inside each inner face.

Fig. 9.1: (a) Plane graph and (b) its octagonal drawing.

An octagonal drawing of a plane graph G has practical applications in VLSI floorplanning. As we have seen in Section 1.5.1, a VLSI floorplan is often considered as a subdivision of a rectangle into a finite number of non-overlapping smaller rectangles, each of which corresponds to a functional entity called a module [Len90, SY99]. A slicing floorplan is often used by VLSI design [Shi96, YS93, YS95]. Divide a rectangle into two smaller rectangles by slicing it vertically or horizontally, divide any subrectangle into two smaller subrectangles by slicing it vertically or horizontally, and so on, as illustrated in Figs. 9.2(a) (e). The resulting floorplan like one in Fig. 9.2(e) is called a slicing floorplan. An underlying...