Rectilinear planar layouts and bipolar orientations of planar graphs (Q1085168)

The authors propose a linear-time algorithm for generating a planar layout of a planar graph in which vertices (edges) are represented by horizontal (vertical) line segments, all endpoints of the segments having integer coordinates. The new algorithm, a variant of one by \textit{Otten} and \textit{van Wijk} [Circuits and Systems, Proc. IEEE Int. Symp. 914-918 (1978)] generally produces a more compact layout and, at the same time allows the dual graph to be laid out in an interlocking way. It is based on the concept of a bipolar orientation of a planar graph G with two distinguished vertices s and t; it is obtained by directing each edge of G so as to obtain a unique source (s) and unique sink (t). Relationships among bipolar orientations of a planar graph are also discussed.