Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-007-85
Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations
Authors: Rosenstiehl, Pierre, Tarjan, Robert E.
Date:July 1985
Pages:19
Download Formats: [PDF]
Abstract:
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 co-ordinates. The total space occupied by the layout is at most n by at most 2n - 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 algorithmis based on the concept of a bipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.