2-tree planar graph drawings now need only logarithmic edge ratios
Logarithmic edge-length ratios for planar drawings of 2-trees
Computational Geometry
Summary
This paper studies how to draw a specific type of network called a 2-tree on a flat surface without the lines crossing. The authors focus on making the longest and shortest lines in the drawing not too different in length. They show that the difference in edge lengths grows only about as fast as the logarithm of the number of points, improving on a previous estimate that suggested a faster growth. This result means clearer and more balanced drawings for 2-trees.
What this means in practice
- •For graph drawing software developers: Design drawing algorithms for 2-tree planar graphs with improved edge length balance to produce clearer visualizations.
- •For network visualization teams: Use guaranteed logarithmic edge length ratios to create more readable network layouts where balanced edge lengths improve comprehension.
A theory result. No direct application yet.
Authors
Zahra Sabaei, Yasmin Tousinejad, Fatemeh Emami
Abstract
For a planar graph $G$ with at least one edge, let $ρ(G)$ be the infimum of the ratio of the longest to the shortest edge length over all planar straight-line drawings of $G$. We prove that every $n$-vertex $2$-tree $G$ satisfies $ρ(G)\le4+5\lfloor\log_2(2n-3)\rfloor$. This improves the known $O(\sqrt n)$ upper bound and, together with the lower bound of Blažej, Fiala and Liotta, shows that the maximum of $ρ(G)$ over $n$-vertex $2$-trees is $Θ(\log n)$. The proof adapts Biedl's recursive bar construction using nonintegral heights and applies a height-preserving straightening theorem.