Universal small point sets improve planar graph drawings
Almost Linear Universal Point Sets for Planar Graphs
Computational Geometry
Summary
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.
What this means in practice
- •For graph drawing software developers: Design point layouts that guarantee crossing-free straight-line drawings of all planar graphs with almost minimal point usage.
- •For data visualization engineers: Create more efficient visualizations of planar networks by using smaller sets of layout points without losing drawing quality.
A theory result. No direct application yet.
Authors
Taylor Gordon
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.