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

DOI10.1016/j.comgeo.2010.03.007zbMath1253.68261OpenAlexW2174713390MaRDI 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 graphsgraph drawingminimum areagrid drawingsstraight-line drawings

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Outer 1-planar graphs ⋮ Drawing Halin-graphs with small height ⋮ Area requirement of graph drawings with few crossings per edge ⋮ 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

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

This page was built for publication: Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area