A LINEAR ALGORITHM FOR 2-BEND EMBEDDINGS OF PLANAR GRAPHS IN THE 2-DIMENSIONAL GRID

In this paper we describe a linear algorithm for embedding planar grap hs in the rectilinear two-dimensional grid, where vertices are grid po ints and edges are noncrossing grid paths. The main feature of our alg orithm is that each edge is guaranteed to have at most 2 bends (with t he single exception of the octahedron for which 3 bends are needed). T he total number of bends is at most 2n + 4 if the graph is biconnected and at most (7/3)n in the general case. The area is (n + 1)(2) in the worst case. This problem has several applications to VLSI circuit des ign, aesthetic layout of diagrams, computational geometry.