Drawing Halin-graphs with small height

DOI10.7155/JGAA.00604zbMATH Open1499.68254arXiv2003.14413OpenAlexW3015049257MaRDI QIDQ5050008FDOQ5050008

Authors: Milap Sheth, Therese Biedl 

Publication date: 14 November 2022

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

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).

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

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

Mathematics Subject Classification ID

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

Cites Work

• How to draw a planar graph on a grid
• A note on optimal area algorithms for upward drawings of binary trees
• Linear area upward drawings of AVL trees
• PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA
• Title not available (Why is that?)
• Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Towards an implementation of the 3D visibility skeleton
• Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
• Title not available (Why is that?)
• VPG and EPG bend-numbers of Halin graphs
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• A 3-approximation for the pathwidth of Halin graphs
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• AREA-EFFICIENT ORDER-PRESERVING PLANAR STRAIGHT-LINE DRAWINGS OF ORDERED TREES
• Title not available (Why is that?)
• Title not available (Why is that?)
• Height-Preserving Transformations of Planar Graph Drawings
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs
• Dominating cycles in Halin graphs
• Tree drawings revisited
• Simple Recognition of Halin Graphs and Their Generalizations
• LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs
• Horton-Strahler number, rooted pathwidth and upward drawings of trees

Cited In (1)

• Drawing Planar Graphs with Reduced Height

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)