Drawing Halin-graphs with small height

DOI10.7155/JGAA.00604MaRDI QIDQ5050008zbMATH OpenOpenAlexFDO

Authors Milap Sheth, Therese Biedl

Publication date 14 November 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.14413

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we study how to draw Halin-graphs, i.e., planar graphs that consist of a tree $T$ and a cycle among the leaves of that tree. Based on tree-drawing algorithms and the pathwidth $pw(T)$, a well-known graph parameter, we find poly-line drawings of height at most $6pw(T)+3inO(logn)$. We also give an algorithm for straight-line drawings, and achieve height at most $12pw(T)+1$ for Halin-graphs, and smaller if the Halin-graph is cubic. We show that the height achieved by our algorithms is optimal in the worst case (i.e. for some Halin-graphs).

Recommendations

• Drawing planar graphs with reduced height
• Drawing Planar Graphs with Reduced Height
• Order-preserving drawings of trees with approximately optimal height (and small width)
• A 3-approximation for the pathwidth of Halin graphs
• A 4-approximation for the height of drawing 2-connected outer-planar graphs

Cites work

• A 3-approximation for the pathwidth of Halin graphs
• A note on optimal area algorithms for upward drawings of binary trees
• AREA-EFFICIENT ORDER-PRESERVING PLANAR STRAIGHT-LINE DRAWINGS OF ORDERED TREES
• Dominating cycles in Halin graphs
• Height-preserving transformations of planar graph drawings
• Horton-Strahler number, rooted pathwidth and upward drawings of trees
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• scientific article; zbMATH DE number 3853133 (Why is no real title available?)
• scientific article; zbMATH DE number 3346402 (Why is no real title available?)
• Linear area upward drawings of AVL trees
• Order-preserving drawings of trees with approximately optimal height (and small width)
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA
• Simple recognition of Halin graphs and their generalizations
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs
• Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Tree drawings revisited
• VPG and EPG bend-numbers of Halin graphs

Cited in

(6)

• Homotopy height, grid-major height and graph-drawing height
• Simple recognition of Halin graphs and their generalizations
• Drawing planar graphs with reduced height
• Drawing Planar Graphs with Reduced Height
• Minimum height drawings of ordered trees in polynomial time: homotopy height of tree duals
• Faster algorithms for grid and layered drawings of plane 3-trees

This page was built for publication: Drawing Halin-graphs with small height

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5050008)