We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at most
n by at most 2
n–4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of a
bipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.
Research partly supported by the Agence de L'Informatique du Ministere de L'Industrie, France, under contract No. 83-285.