Papers for

graph drawing software developers

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.

Linear time test finds bend free drawings for special planar graphs

Linear-Time FPT Rectilinear Planarity Testing of Series-Parallel Graphs

Abstract: A planar graph is rectilinear planar if it admits a planar orthogonal drawing without bends. For series-parallel graphs in the variable embedding setting the best known testing algorithm takes $O(n^2)$ time. We show that rectilinear planarity of a series-parallel graph with maximum degree four can be tested in $2^{O(k)}\cdot n$ time, where $k$ is the number of degree-4 vertices; the planar embedding is not fixed. In particular, the running time is subquadratic when $k=o(\log n)$. Each node of the SPQ$^*$-tree stores the set of its admissible spiralities; we show that this set is a union of $2^{O(k)}$ arithmetic progressions of step two. All proofs are in the paper and are additionally verified in Lean 4 with Mathlib.

Tue 27 OctData Structures and Algorithms
The gist
Some graphs can be drawn on paper with only straight horizontal and vertical lines and no bends, which can be useful for clear diagrams. Testing if such a drawing exists usually takes a long time for certain graphs. The authors show a way to do this test much faster for a special kind of graph called series-parallel graphs with a limited number of points having four connections. They use a clever mathematical structure and prove their results with computer verification. This means certain clean drawings can now be checked more quickly.
Open → 2610.37018v1

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

Archdeacon conjecture bounds nonplanar quadruples in rotation systems

Some results on Archdeacon's conjecture for rotation systems

Abstract: A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

Thu 10 SeptComputational Geometry
The gist
A rotation system arranges elements so their connections have a circular order. The paper studies how many groups of four elements must create some unavoidable 'crossings' in such systems, a problem linked to drawing complete graphs without overlaps. The authors confirm a longstanding conjecture for small sizes using computers and provide approximate bounds for larger sizes, partly by hand. They also prove the conjecture for a certain special class of these systems. This helps understand the limits of how 'tangled' such arrangements must be.
Open → 2609.11599v1

Universal small point sets improve planar graph drawings

Almost Linear Universal Point Sets for Planar Graphs

Abstract: A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

Thu 10 SeptComputational Geometry
The gist
Drawing any network without lines crossing can be tricky. The authors found a way to pick almost the smallest number of points needed so that any network with a certain number of points can be drawn without overlaps using those points. They built on earlier work linking these drawings to special sequences called permutations. This helps to better understand how to arrange points for neat network drawings.
Open → 2609.10916v1