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

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.