Rectilinear planar layouts and bipolar orientations of planar graphs

Pierre Rosenstiehl, Robert Endre Tarjan

Research output: Contribution to journalArticle

209 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)343-353
Number of pages11
JournalDiscrete & Computational Geometry
Volume1
Issue number1
DOIs
StatePublished - Dec 1 1986

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Rectilinear planar layouts and bipolar orientations of planar graphs'. Together they form a unique fingerprint.

  • Cite this