Linear time test finds bend free drawings for special planar graphs
Linear-Time FPT Rectilinear Planarity Testing of Series-Parallel Graphs
Data Structures and Algorithms
Summary
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.
What this means in practice
- •For circuit designers: Check if circuit layouts with no bends are possible faster for series-parallel connection patterns, improving early-stage design verification.
- •For graph drawing software developers: Incorporate efficient bend-free layout testing for series-parallel graphs with few complex nodes, enabling smoother interactive graph visualization.
A theory result. No direct application yet.
Authors
Giacomo Ortali
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.