8.1 Introduction

An orthogonal drawing of a plane graph G is a drawing of G, with the given embedding, in which each vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end, as illustrated in Fig. 8.1. Orthogonal drawings have numerous practical applications in circuit schematics, data flow diagrams, entity relationship diagrams, etc., as mentioned in Chapter 1. Clearly the maximum degree ? of G is at most four if G has an orthogonal drawing. Conversely, every plane graph with ? ?4 has an orthogonal drawing, but may need bends, that is, points where an edge changes its direction in a drawing. For the cubic plane graph in Fig. 8.1(a), two orthogonal drawings are depicted in Figs. 8.1(b) and (c), which have six and five bends, respectively. If a graph corresponds to a VLSI circuit, then one may be interested in an orthogonal drawing such that the number of bends is as small as possible, because bends increase the manufacturing cost of a VLSI chip. However, for a given planar graph G, if one is allowed to choose its planar embedding, then finding an orthogonal drawing of G with the minimum number of bends is NP-complete [GT01]. On the other hand, Tamassia [Tam87] and Garg and Tamassia [GT97] presented algorithms which find an orthogonal drawing of a given...