Universal Point Sets

Subquadratic Universal Point Sets

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A finite set $S\subset{\mathbb{R}}^2$ is universal for $n$-vertex planar graphs if every such graph has a crossing-free straight-line drawing whose vertex positions belong to $S$. The selected $n$ points and their assignment may depend on the graph. Seek sets $S_n$ with $|S_n|=o(n^2)$. The points need not have integer coordinates. [S1] [S2]

Statement recorded in the supplied source.

Do planar graphs have universal point sets of subquadratic size? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Construct an $o(n^2)$-size universal point set for all n-vertex planar graphs, or prove a quadratic lower bound. [S1]

Short English statement

Can one set of substantially fewer than n-squared plane points support straight-line planar drawings of every n-vertex planar graph?

Research attempt

Status: UNRESOLVED. We construct a universal set of exactly $n$ points for all $n$-vertex trees, prove that no entirely convex point set is universal for all planar graphs once $n\ge4$, and isolate the quantifier obstacle in combining graph-specific drawings.

Source check.

Felsner--Schrezenmaier--Schröder--Steiner [S4], primary abstract consulted 1 October 2026, gives linear-size sets for bipartite planar graphs and planar graphs of maximum degree three. Those subclasses do not exhaust planar graphs. The elementary construction below concerns trees and does not duplicate the stronger cited theorem. The target asks for one point set for every graph of the given order; allowing a different point set for each graph would remove its main difficulty.

A convex $n$-point set supports every tree.

Take any $n$ points in strictly convex position, with a chosen cyclic order. Root the tree at an arbitrary vertex and list its vertices in depth-first preorder, choosing an arbitrary order of the children at every vertex. Map this list in order to the convex points and draw each tree edge as a straight segment.

To verify that edges do not cross, every rooted subtree occupies a contiguous block in the preorder list. For an edge from a parent to a child, all vertices listed strictly between those two endpoints lie in earlier child subtrees of that parent. Any edge having an endpoint in one of those earlier subtrees has its other endpoint in the same subtree or at that parent; it cannot have its other endpoint strictly beyond the later child while remaining disjoint from the parent-child edge's endpoints. Edges entirely inside a later subtree likewise have both endpoints after that child. Thus two vertex-disjoint tree edges never have alternating endpoints around the convex polygon.

Two chords of a strictly convex polygon cross in their interiors exactly when their four endpoints alternate around its boundary: one chord separates the polygon into two sides, and the other crosses it precisely when its endpoints lie on opposite sides. Applying this criterion proves that the drawing is crossing-free. No three convex-position vertices are collinear, so no edge passes through a third vertex. This establishes a universal set of size $n$ for trees.

The construction permits its vertex assignment to depend on the tree, as the problem allows. It does not assert that every fixed assignment of a tree to the points is plane; a bad ordering can create alternating endpoints.

The construction is optimal for trees by cardinality.

A straight-line drawing uses distinct points for distinct vertices, so any set universal for even one $n$-vertex graph must have at least $n$ points. The convex construction therefore has minimum possible cardinality for the tree subclass. Disconnected forests can be handled by ordering their components in consecutive blocks and applying the same argument within each block.

This cardinality lower bound remains valid for the full planar-graph class, but it is only linear and gives no evidence of a quadratic lower bound. In particular it cannot refute the requested $o(n^2)$ possibility.

Why adding more points in convex position still fails.

For $n\ge4$, consider the planar graph consisting of $K_4$ together with $n-4$ isolated vertices. Any four selected points from a strictly convex point set are themselves in convex position. The two diagonals among those four points are edges of their $K_4$, and they cross. Therefore no all-convex point set, regardless of its cardinality, is universal for this graph.

The obstruction is geometrical placement, not a lack of sufficiently many points. A planar straight-line drawing of $K_4$ instead requires one of its vertices inside the triangle formed by the other three. Thus a universal set for the full class must offer appropriate interior structure. Merely putting additional points on the same convex curve cannot repair the tree construction.

A union of drawings and its counting limitation.

For each planar graph on $n$ labelled vertices, the straight-line drawing theorem supplies some plane drawing. Taking a disjointly translated union of the vertex sets of one drawing for each graph yields a finite universal point set. This argument uses the classical straight-line drawing theorem as an external existence input, and does not give a useful small bound: there are at most $2^{\binom n2}$ labelled graphs, so the crude union can have $n2^{\binom n2}$ points.

The reason this observation is not an asymptotic solution is explicit. Coordinates can depend arbitrarily on the graph, and the union pays for that dependence by allocating separate points. A subquadratic construction must share a much smaller supply of points across all graph types while still permitting graph-dependent assignments. Conversely, counting labelled graphs alone does not yield a quadratic lower bound, because one fixed point set can support many different plane edge sets and many assignments.

Verification and exact remaining gap.

The tree proof reduces every possible edge crossing to a forbidden alternation in a preorder interval, including nested subtrees. The $K_4$ obstruction holds for every four-point subset of an all-convex set, not just four consecutive points. No drawing search or optimality claim for general planar graphs is made.

The unresolved step is a point arrangement with $o(n^2)$ points that supports arbitrary planar nesting and adjacency patterns, or a proof that no such arrangement exists. The contrast between the exact tree construction and the four-vertex obstruction identifies the first geometric feature a successful construction must add: interior points usable in many different enclosing triangles. It does not establish that a bounded number of such layers suffices.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1409 (GRAPH-022), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 M. Bannister, Z. Cheng, W. Devanny, and D. Eppstein, Superpatterns and Universal Point Sets, Journal of Graph Algorithms and Applications 18 $2014$, 177–209. https://doi.org/10.7155/jgaa.00318. Bibliographic information from the supplied record.

• S3 M. Scheucher, H. Schrezenmaier, and R. Steiner, A Note on Universal Point Sets for Planar Graphs, Journal of Graph Algorithms and Applications 24 $2020$, 247–267. https://doi.org/10.7155/jgaa.00529. Bibliographic information from the supplied record.

• S4 S. Felsner, H. Schrezenmaier, F. Schröder, and R. Steiner, Linear Size Universal Point Sets for Classes of Planar Graphs, arXiv:2303.00109 $2023$. https://arxiv.org/abs/2303.00109. Bibliographic information from the supplied record.