A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid (Q1382254): Difference between revisions

It is well known that every \(n\)-vertex planar graph of maximum degree at most 4 has a drawing in the plane such that its vertices are points of the integer grid and its edges are nonintersecting paths in the grid graphs. Moreover, each edge may be required to have at most four bends. In this paper, a linear time algorithm is presented which produces such a drawing with at most two bends per edge (with the only exception among connected graphs being the octahedron for which three bends are necessary), and so that the number of bends is at most \(7n/3\). Moreover, the drawing can be enclosed in a rectangle with area \((n+1)^2\).