Source-linked AI summary
Almost Linear Universal Point Sets for Planar Graphs
Taylor Gordon
TL;DR
The paper asks how small a point set can serve every planar graph on n vertices; earlier general bounds were quadratic while lower bounds were linear. It reduces the upper bound to n^1+o(1) by constructing superpatterns through ordered forests and intervals.
Problem
How small can a point set be while supporting a crossing-free straight-line drawing of every planar graph on n vertices?
Source: §1 · p. 1Method
Results
The construction establishes u(n) = n^1+o(1), improving the previous quadratic general upper bound.
Source: §1 · pp. 1–2Takeaways & Limitations
The general upper bound is now within a subpolynomial factor of the linear lower bounds, but whether u(n) = O(n) remains open.
Source: §1 · p. 2Whether u(n) = O(n) remains open, and the point-count bound does not bound total coordinate encoding length.
Source: §5 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks how small a point set can support crossing-free straight-line drawings of every planar graph on n vertices. It establishes u(n) = n^1+o(1) through a superpattern construction, while leaving the linear-bound question open.
1 Introduction
- The earlier general upper bound was quadratic, while known lower bounds were linear, leaving a substantial gap.The cited lower bound is (1.293 −o(1))n; prior general upper bounds remained quadratic in the 2025 survey.Source: §1 · pp. 1–2
- u(n) = n^1+o(1), reducing the gap between linear lower bounds and the previous quadratic general upper bound.The result concerns the number of points, not grid placement, drawing area, or coordinate magnitude.Source: §1 · pp. 1–2
- The paper does not settle whether u(n) = O(n).Its point-count bound does not imply a comparable bound on drawing area or coordinate magnitude.Source: §1 · p. 2
- The construction reduces universal point sets to permutation superpatterns, then represents 213-avoiding permutations by ordered rooted forests contained in a small interval family.The reduction is due to Bannister et al..Source: §1 · p. 2
2 Superpatterns and Ordered Forests
The section connects 213-avoiding permutations to ordered rooted forests and uses interval representations to obtain superpatterns. Those superpatterns feed the reduction to universal point sets.
2 Superpatterns and Ordered Forests
- An Sn−3(213)-superpattern of length M yields a universal point set of size M + 3 for planar graphs on n vertices.The reduction adds three entries and uses coordinate stretching to obtain a crossing-free drawing.Source: §2 · p. 3
- An ordered rooted forest orders its roots and each vertex’s children, and represents each vertex by an interval nested inside its ancestors’ intervals.Intervals of incomparable vertices are disjoint, occur in the prescribed order, and have a positive gap.Source: §2 · p. 3
- Every ordered rooted forest on n vertices can be represented within a family of M intervals to obtain an Sn(213)-superpattern of length M.The figure illustrates a forest and interval representation whose endpoint ranks give permutation 24531.Source: §2 · p. 3, Figure 1 · p. 4
- For a 213-avoiding permutation, the predecessor relation forms a rooted forest whose preorder is the permutation’s index order.The predecessors of each entry form a chain, and the roots and children are ordered by their indices.Source: §2 · p. 4
- In an interval representation, the points formed from left endpoints and negated right endpoints have the forest’s permutation pattern.Sorting the full interval family by left endpoints and ranking right endpoints in decreasing order produces a permutation containing the represented patterns.Source: §2 · p. 4
3 Layered Intervals
The layered construction assigns intervals according to subtree size, with radii and midpoint grids chosen to support ordered packing. Packing estimates control the space needed for the trees.
3 Layered Intervals
- Intervals are assigned by subtree size: layer i uses radius Ri and midpoint locations on the grid ciZ.The spacing choice makes ci divide cj whenever i ≤ j, so translating a tree by a multiple of its root spacing preserves descendant grids.Source: §3 · pp. 4–5
- The finite family includes intervals [jci − Ri, jci + Ri] for layers i and grid positions j up to 2W/ci.The grids and W are powers of two, with ci ≤ W; representations near zero are translated by W into the family’s range.Source: §3 · p. 5
- Ordered trees with root midpoint zero can be translated into a bounded interval in their prescribed order while preserving layers and grids.The packing lemma also permits packing them in the reverse direction into [z −B, z −1].Source: §3 · p. 5
- The packing estimates use an increasing convex function F and a space-between-layers bound for integer t ≥ 10.The derivative of F jumps from 8 on the left of 1 to 12 on the right, and F′(x) ≥ 12 for x ≥ 1.Source: §3 · p. 5
4 Embedding Trees and Forests
The construction embeds each ordered rooted tree in a prescribed interval using layers indexed by subtree size, then combines those tree representations to embed any ordered rooted forest.
4 Embedding Trees and Forests
- Each ordered rooted tree on t vertices has a layered interval representation with root interval [−Rt, Rt], and each vertex uses the layer indexed by its subtree size.The induction packs child intervals inside the prescribed root interval.Source: §4 · p. 6
- When a child is dominant, its root stays centered while the other children pack to either side; without one, ordinary packing fits the children inside the root interval.A dominant child has size greater than t − δ, so there can be at most one.Source: §4 · pp. 6–7, Figure 2 · p. 7
- The root is centered at zero, and the available space around its interval suffices to pack preceding and following children in order with positive gaps.This completes the inductive placement within the prescribed root interval.Source: §4 · p. 7
- Every ordered rooted forest on n vertices has a layered interval representation contained in [−Rn, Rn], using only layers 1 through n.The proof represents its trees individually, then packs their root intervals into the forest envelope.Source: §4 · p. 7
- For small forests with multiple roots, convexity bounds the combined packing capacity so the roots fit inside the same envelope.For 2 ≤ n ≤ 9, the proof uses a separate bound to establish this packing.Source: §4 · pp. 7–8
5 Counting the Intervals
Theorem 2 bounds the length of the constructed 213-superpattern by counting intervals across dyadic layers. Translating the forest embeddings into the interval family gives the superpattern, while the universal-point-set bound does not settle linear size.
5 Counting the Intervals
- Theorem 2 gives a subpolynomial-factor-scale bound on the length of the constructed superpattern for Sn(213).The displayed bound is expressed using 2 + ⌈log2 n⌉ and n log(n + 1).Source: §5 · p. 8
- Translating the forest embeddings by W places their intervals in In, and Lemma 2 turns that family into a superpattern.The grid spacings divide W, and the translated midpoints lie in [0, 2W].Source: §5 · p. 8
- The interval count sums layer contributions: layer 1 contributes 1 to the reciprocal-spacing sum, and each complete dyadic block contributes 1/2.Each layer contains exactly 1 + 2W/ci intervals.Source: §5 · p. 8
- The point bound concerns the number of points, not the area of a drawing or the magnitude of its coordinates.The final stretching may produce coordinates with many more bits, so the point-count bound does not bound total binary encoding length comparably.Source: §5 · p. 8
- The superpattern bound is within a subpolynomial factor of the known Ω(n log n) superpattern lower bound, but whether u(n) = O(n) remains open.The reduction is one-way and does not establish a superlinear lower bound for arbitrary universal point sets.Source: §5 · p. 8
A From Superpatterns to Universal Point Sets
The appendix presents the reduction of Bannister, Cheng, Devanny, and Eppstein from a 213-superpattern to a universal point set. The reduction applies even when the superpattern itself does not avoid 213.
A From Superpatterns to Universal Point Sets
- The reduction applies to an arbitrary Sn−3(213)-superpattern; the host permutation need not avoid 213.The construction is due to Bannister, Cheng, Devanny, and Eppstein [6, Section 3].Source: A From Superpatterns to Universal… · p. 9
- Given a superpattern σ of length M, the construction forms τ by adding entries 1 and 2 around the shifted entries of σ.It sets Q = M + 3 and uses τ = (1, Q, σ1 + 2, . . . , σM + 2, 2).Source: A From Superpatterns to Universal… · p. 9
- The resulting universal point set has M + 3 points, and the appendix proves these points suffice.The passage identifies the point-set size and the sufficiency claim, but does not give the point coordinates here.Source: A From Superpatterns to Universal… · p. 9
A.1 The canonical permutation
The appendix constructs an ordered spanning tree from a canonical vertex insertion order and derives two traversal orders of its vertices. These orders encode ancestry in a permutation that avoids 213.
A.1 The canonical permutation
- The canonical insertion order grows a maximal plane graph from an outer triangle, with each new vertex attaching to a consecutive boundary block.The construction chooses the first earlier neighbor along the boundary path as the new vertex's parent.Source: §A.1 · p. 9
- The ordered spanning tree places each new vertex first in its parent's child list, and p is its preorder rank.The order of the boundary path remains increasing in p as vertices are inserted.Source: §A.1 · p. 9
- The reverse-postorder rank r is also a canonical order with the same boundary preorder property [6, Lemma 15].The passage justifies this by orienting graph edges and showing that swaps of consecutive incomparable vertices preserve the ordered tree.Source: §A.1 · pp. 9–10
- For distinct vertices, u is an ancestor of v exactly when both p(u) < p(v) and r(u) < r(v).The two traversal orders together characterize ancestry.Source: §A.1 · p. 10
- Defining π by πp(v) = r(v) yields a 213-avoiding permutation, since such a pattern would contradict the two-order ancestry characterization.The passage connects a 213 occurrence to two incomparable ancestors of its last vertex.Source: §A.1 · p. 10
A.2 Why the stretching prevents crossings
The proof uses height-based orientation to characterize segment crossings, then applies that criterion to rule out crossings between disjoint graph edges.
A.2 Why the stretching prevents crossings
- With X_i=(i, Q^τ_i), the determinant D tests whether a highest point lies above the line through two others; its positivity establishes the orientation rule.Source: §A.2 · p. 10
- Two segments X_hX_j and X_iX_k cross exactly when h<i<j and τ_i<max{τ_h,τ_j}.Source: §A.2 · p. 10
- A proposed crossing of disjoint edges yields rank inequalities that lead to a contradiction, proving that disjoint edges do not cross.The inequalities are p(u)<p(w)<p(v) and r(w)<max{r(u),r(v)}<r(z′).Source: §A.2 · p. 11
A.3 The size of the coordinates
The explicit point-set coordinates have a large expanded binary representation, so the point-count bound does not also bound coordinate-description size.
A.3 The size of the coordinates
- Formula (9) explicitly describes the point set.Source: §A.3 · p. 11
- The largest ordinate is Q^Q and requires Θ(Q log Q) bits.Source: §A.3 · p. 11
- Expanded ordinates total Θ(Q^2 log Q) bits, and Theorem 1 does not claim a near-linear bound on coordinate length or grid area.Source: §A.3 · p. 11