Papers for

network visualization teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

2-tree planar graph drawings now need only logarithmic edge ratios

Logarithmic edge-length ratios for planar drawings of 2-trees

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.

Tue 20 OctComputational Geometry
The gist
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.
Open → 2610.28030v1