A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid

DOI10.1016/S0166-218X(97)00076-0zbMath0912.68153OpenAlexW2012855423MaRDI QIDQ1382254

Yanpei Liu, Aurora Morgana, Bruno Simeone

Publication date: 18 May 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(97)00076-0

zbMATH Keywords

drawinglinear time algorithmplanar graphgrid graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Single bend wiring on surfaces ⋮ A graph partition problem ⋮ Unnamed Item ⋮ Universal slope sets for 1-bend planar drawings ⋮ Unit-length rectangular drawings of graphs ⋮ Computational complexity of jumping block puzzles ⋮ Orthogonal drawings of graphs for the automation of VLSI circuit design ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ Bend-minimum orthogonal drawings in quadratic time ⋮ Orthogonal graph drawing with flexibility constraints ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ Balanced vertex-orderings of graphs ⋮ Computational complexity of jumping block puzzles ⋮ Grid straight-line embeddings of trees with a minimum number of bends per path ⋮ On the two-dimensional orthogonal drawing of series-parallel graphs ⋮ An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid ⋮ Boolean approaches to graph embeddings related to VLSI ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• General theoretical results on rectilinear embeddability of graphs
• Multilayer grid embeddings for VLSI
• Orientations with single source and sink
• A unified approach to visibility representations of planar graphs
• The complexity of minimizing wire lengths in VLSI layouts
• A new approach to the linearity of testing planarity of graphs
• st-ordering the vertices of biconnected graphs
• Planar graphs: Theory and algorithms
• Computing an st-numbering
• On minimal-node-cost planar embeddings
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Universality considerations in VLSI circuits
• Efficient Planarity Testing
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid