Small area drawings of outerplanar graphs

DOI10.1007/s00453-007-9117-3zbMath1171.68029OpenAlexW2008443107MaRDI QIDQ1024211

Fabrizio Frati, Giuseppe Di Battista

Publication date: 16 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9117-3

zbMATH Keywords

balanced outerplanar graphsplanar straight-line grid drawings of outerplanar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Outer 1-planar graphs ⋮ Area requirement of graph drawings with few crossings per edge ⋮ Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs ⋮ Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area ⋮ Polynomial area bounds for MST embeddings of trees ⋮ Universal point sets for planar three-trees ⋮ Small grid drawings of planar graphs with balanced partition ⋮ LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs ⋮ Improved Upper and Lower Bounds for LR Drawings of Binary Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for drawing a planar graph on a grid
• How to draw a planar graph on a grid
• Area-efficient planar straight-line drawings of outerplanar graphs
• A near-linear area bound for drawing binary trees
• Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
• Universality considerations in VLSI circuits
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Graph Drawing