Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area

DOI10.1016/j.comgeo.2010.03.007zbMath1253.68261MaRDI QIDQ452455

Fabrizio Frati

Publication date: 21 September 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.03.007

zbMATH Keywords

outerplanar graphs; graph drawing; minimum area; grid drawings; straight-line drawings

Mathematics Subject Classification ID

68U10: Computing methodologies for image processing

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Drawing Halin-graphs with small height, Outer 1-planar graphs, A linear-time algorithm for testing outer-1-planarity, LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, Area requirement of graph drawings with few crossings per edge

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to draw a planar graph on a grid
• Area-efficient planar straight-line drawings of outerplanar graphs
• Small area drawings of outerplanar graphs
• A note on optimal area algorithms for upward drawings of binary trees
• Triangulating planar graphs while minimizing the maximum degree
• Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n logn) Area (Extended Abstract)
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Graph Drawing
• A Note on Minimum-Area Straight-Line Drawings of Planar Graphs
• Graph Drawing