Homotopy height, grid-major height and graph-drawing height

2019/08/15 by Biedl, Therese, Chambers, Erin Wolf, Eppstein, David +2 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1908.05706

Abstract

It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two other parameters, the (simple) homotopy height and the (simple) grid-major height. We discuss the relationship between them and to the other parameters, and argue that they give lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity.

Cited by

• Sweeping x-monotone pseudolines

Related

• Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals
• A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings
• On Upward Drawings of Trees on a Given Grid
• Transforming planar graph drawings while maintaining height
• Order-preserving drawings of trees with approximately optimal height (and small width)