An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs

Alexander Choi; Kevin Costello; Marek Chrobak

REVIEW 1 major objections 4 minor 12 references

An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random point sets require Ω(n²) points to be universal for all planar graphs.

desk verdict A clean negative result showing uniform random point sets need quadratic size to be n-universal, with a new monotone-subset structural lemma and a standard union bound; the one loosely justified topological step is real but repairable. read the letter →

arxiv 1908.07097 v2 pith:ADBGHYG3 submitted 2019-08-19 cs.DM cs.CGmath.CO

Alexander Choi , Marek Chrobak , Kevin Costello This is my paper · ORCID

classification cs.DMcs.CGmath.CO MSC 05C1005C6260C0505A05

keywords planargraphsuniversalpointsetsstraight-lineembeddingsprobabilisticmethodrandompermutationslongestmonotonesubsequencelowerboundsnestedtriangles

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether the probabilistic method can prove the existence of small universal point sets: point sets into which every n-vertex planar graph can be drawn with straight, non-crossing edges. It answers no for the basic version of the method. If $m$ points are chosen independently and uniformly from the unit square and $m$ is at most $(n/(48e))^2$, the resulting set fails to be $n$-universal with probability at least $1 - 8\cdot 4^{-n/12}$. The obstruction is that any $n$-universal set must contain a monotone subset of size about $n/12$, whereas random sets of that size almost surely contain no such subset. Hence the probabilistic method in its simplest form cannot deliver universal sets of size $o(n^2)$.

What carries the argument

The load-bearing object is a maximal planar graph $G_0$ built from $2k = n/3$ vertex-disjoint 3-cycles $C_1,\ldots,C_{2k}$, with consecutive layers connected so that the graph is 3-connected. A classical uniqueness result for 3-connected planar graphs forces any straight-line embedding to have, up to choice of the outer face, either the first $k$ or the last $k$ cycles appearing as nested triangles $T_1,\ldots,T_k$. The axis-parallel bounding boxes of these nested triangles are also nested, and each box contributes at least one corner that belongs to the universal set; those corners split into an increasing chain and a decreasing chain, giving a monotone subset of size $k/2 = n/12$. On the probabilistic side, the machinery is the correspondence between random point sets and uniform random permutations, together with a union-bound estimate, using Stirling's formula, that bounds the probability of a long monotone subsequence by $2\cdot(me^2/\ell^2)^\ell$ with $\ell = \lfloor n/12\rfloor$. This probability is small when $m \le (n/(48e))^2$ because then $\ell \ge 2e\sqrt{m}$.

What would settle it

Compute the exact frequency of monotone subsequences of length $\lfloor n/12\rfloor$ in uniform random permutations of $m = \lfloor (n/(48e))^2\rfloor$ elements for a range of $n$; Claim 3 predicts a frequency no larger than $8\cdot 4^{-n/12}$, so any $n$ where the observed frequency exceeds that bound refutes the probabilistic half. Separately, search for a straight-line embedding of the stacked-triangle graph $G_0$ in which neither the first nor the last half of its cycles forms a nested chain; one such embedding would refute Lemma 2 and with it the theorem's geometric reduction.

Watch

Extended reading notes

Core claim

The paper proves Theorem 1: a set of $m$ points chosen uniformly and independently from the unit square is $n$-universal with probability tending to zero unless $m$ is quadratic in $n$. Concretely, for $m \le (n/(48e))^2$ the failure probability is at least $1 - 8\cdot 4^{-n/12}$. The proof proceeds by establishing a deterministic necessary condition (Lemma 2): every $n$-universal set contains a monotone subset of cardinality $\lfloor n/12\rfloor$. It then shows that a uniform random $m$-point set induces a uniform random permutation, and a uniform random permutation of $m \le (n/(48e))^2$ elements contains a monotone subsequence of length $\lfloor n/12\rfloor$ with probability at most $8\cdot 4^{-n/12}$. The theorem is therefore a lower bound specific to sets produced by the basic probabilistic method; the paper notes explicitly that other distributions or more refined arguments could still yield $o(n^2)$-size universal sets.

Load-bearing premise

The proof depends on the unproved topological assertion that every straight-line drawing of its layered triangle graph contains a long chain of nested triangles, whichever face is chosen as the outside; if a drawing could avoid such a chain, the forced monotone subset would not exist.

Editorial extensions

If this is right

Any $n$-universal set must contain a monotone subset of size $\lfloor n/12\rfloor$; this is a deterministic structural restriction, not merely a property of random sets.
A uniformly random set of $m \le (n/(48e))^2$ points fails to be $n$-universal with probability at least $1 - 8\cdot 4^{-n/12}$, so $m = \Omega(n^2)$ is necessary for the basic probabilistic method to work.
The basic probabilistic method, in which one samples a random point set and hopes it is universal, cannot produce an $o(n^2)$ upper-bound construction for universal point sets.
The theorem does not rule out other probability distributions: a different distribution over point sets of size $o(n^2)$ could still be universal with high probability, and the paper explicitly leaves that possibility open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because Lemma 2 is deterministic, every universal set must have a longest monotone subsequence of length at least $n/12$. Any $m$-point set already has a monotone subsequence of length at least $\sqrt{m}$, so the lemma alone does not force a quadratic deterministic lower bound; however, combining it with stronger structural constraints on universal sets might push deterministic lower bounds beyond
The proof's reduction to random permutations is the bottleneck: if one could design a distribution over point sets whose induced permutation distribution has much shorter longest monotone subsequences than uniform random points, the theorem's obstruction could be bypassed, pointing to a concrete search direction for subquadratic universal sets.
The nesting assertion of Lemma 2 is stated without a proof in the manuscript; verifying it or finding a counterexample would be the quickest way to test whether the random lower bound extends to arbitrary universal sets.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's a quick take on arXiv:1908.07097. The paper proves that a uniformly random set of m points in the unit square, with m ≤ (n/48e)^2, is almost surely not n-universal. So the basic probabilistic method cannot produce o(n^2) universal sets. The result is new and the proof is mostly elementary and self-contained.

The main structural novelty is Lemma 2: any n-universal set must contain a monotone subset of size n/12. The argument builds a maximal planar graph G0 from a stack of 2k triangles, uses Whitney's theorem to get a unique embedding up to the outer face, and then extracts nested triangles, whose axis-parallel bounding boxes force either an increasing or a decreasing subset. This is a neat reduction. The rest is a standard union bound on random permutations: each length-ell subset is monotone with probability 2/ell!, and the bound follows from Stirling's inequality.

The soft spot is in Lemma 2. The paper asserts, without proof, that in any embedding of G0, no matter which face is the outer face, either the first k or the last k triangles appear as nested triangles. This is the load-bearing step connecting graph universality to monotone subsequences. The statement is plausible—the graph is a chain of octahedra, and the cycles form a laminar family on the sphere—but the paper doesn't give the topological argument. A referee should ask for it. Having checked, the claim is true: choosing the point at infinity in the region between C_j and C_{j+1} makes one side a nested chain of length at least k. So it's a rigor gap, not a false step. Other minor issues: a few typos (e.g., 'straighforward', the formula in Claim 3 has a misplaced parenthesis) and the graph construction could be described more precisely.

I don't see any circularity or fatal flaw. The paper is honest that the result only rules out the uniform distribution and does not improve the known (1.293-o(1))n lower bound for arbitrary universal sets. The citation pattern looks fine; the use of Frieze's union bound is credited.

Who is this for? Researchers in graph drawing and universal point sets. It's a short, clean negative result that settles a natural question about the probabilistic method. It deserves a serious referee. I'd accept it for a workshop or journal after minor revision—the missing nesting proof needs to be added.

Referee Report

1 major / 4 minor

Summary. The paper proves that a random set Q of m points drawn uniformly and independently from the unit square is n-universal with probability at most 8·4^{-n/12} whenever m ≤ (n/(48e))^2, yielding an Ω(n^2) lower bound for universal sets produced by the basic probabilistic method. The proof constructs a maximal planar graph G0 consisting of a stack of 2k = n/3 triangles, invokes Whitney's theorem to fix the embedding up to the choice of the outer face, and argues that any embedding forces a long chain of nested triangles. This chain is converted, via axis-aligned bounding boxes, into a monotone subset of U of size at least n/12. Finally, a union bound over all subsets shows that a random permutation of m elements contains a monotone subsequence of length n/12 with probability at most 8·4^{-n/12}.

Significance. The result is a clean negative statement: it rules out the plain probabilistic method as a route to o(n^2) universal sets. The proof is self-contained and elementary, and the reduction from planar embeddings to monotone subsequences via nested triangles and bounding boxes is elegant. The counting argument in Claim 3 is standard but correctly executed. The main weakness is that a key topological assertion in Lemma 2 is stated without proof; this is a genuine rigor gap, though the assertion appears to be true. If the gap is filled, the paper is a solid, modest contribution to the lower-bound literature on universal point sets.

major comments (1)

[Lemma 2, second paragraph] The assertion that, no matter which face of G0 is chosen as the external face, either the first k or the last k of the cycles C1,...,C2k are embedded as nested triangles is load-bearing but is not proved. If a universal set admitted an embedding of G0 without such a long nested chain, the monotone subset argument would collapse. The claim is plausible — G0 is a stack of octahedra and the cycles form a laminar family of disjoint simple closed curves on the sphere — but the parenthetical remark is not a proof. Please add a rigorous topological argument, for example by showing that in any spherical embedding the cycles are pairwise disjoint and that choosing the point at infinity in the annulus between C_j and C_{j+1} yields two chains of nested triangles whose lengths sum to 2k, so one chain has length at least k.

minor comments (4)

[Lemma 2, first paragraph] The reduction to n' = n − (n mod 12) should explicitly note that an n-universal set is also n'-universal for n' < n, since vertices can always be added and placed arbitrarily in an embedding.
[Lemma 2, first paragraph] The proof assumes that no two points of U share an x- or y-coordinate. This is not true of an arbitrary universal set, but the gap is easily fixed by observing that a sufficiently small rotation preserves universality and makes the coordinates distinct; please state this explicitly.
[Claim 3 proof] The displayed chain of inequalities has a formatting error: the step after the second ≤ should read '≤ 2 · (me^2/(2e√m)^2)^ℓ = 2 · 4^{−ℓ}', with the exponent restored. The mathematical argument is correct, but the typesetting is confusing.
[References and text] References: in [7], the title should be 'On straight line representation of planar graphs' rather than 'n straight line representation of planar graphs'. Also, 'straighforward' appears twice and should be corrected to 'straightforward'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the random-set lower bound is derived from a concrete graph construction, a standard uniqueness theorem, and an independent union bound on random permutations.

full rationale

The paper's derivation is self-contained and does not reduce any claimed prediction to its own inputs. Theorem 1 asserts a lower bound for random point sets; the proof constructs a fixed maximal planar graph G0, invokes Whitney's uniqueness theorem and Fáry's theorem as external background, argues that any universal set must contain a monotone subset of size floor(n/12), and then proves, via a union bound, that a random permutation of size at most (n/(48e))^2 has a monotone subsequence of that length with only exponentially small probability. No parameter appearing in the theorem is fitted from the data it is said to predict; the constants are chosen for simplicity and the bound on monotone subsequences is derived from an elementary counting argument attributed to Frieze and reproduced in full. The self-citations (e.g., Chrobak-Karloff, grid-drawing papers) concern background upper and lower bounds and are not load-bearing for the new result. The only potentially vulnerable step is the unproved topological claim in Lemma 2 that, in any plane embedding of G0, either the first k or the last k cycles must appear as nested triangles; this is a rigor gap or a missing proof, not a circularity, because the claim is not equivalent to the theorem's conclusion and does not presuppose the random-set lower bound. Accordingly, the paper receives a circularity score of 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on standard graph theory (Fary, Whitney), a specific geometric claim about nested triangles, and a standard probability fact. No free parameters are fitted to data; the constants 48e and 1/12 are chosen for proof convenience. The paper introduces no new physical or mathematical entities beyond the constructed graph G0.

assumptions (7)

standard math Fary's theorem: every planar graph has a straight-line embedding.
Used in the introduction to establish that finite universal sets exist and to justify focusing on straight-line embeddings.
standard math Whitney's theorem: 3-connected planar graphs have an embedding unique up to the outer face.
Invoked in Lemma 2 to argue the stack-of-triangles graph has a fixed combinatorial embedding as nested triangles.
domain assumption The stack-of-triangles graph G0 with 2k triangles is maximal planar and 3-connected.
Asserted in Lemma 2 with the note that removing two vertices destroys at most four edges between layers; the reader must verify the graph's connectivity.
domain assumption In any planar embedding of G0, either the first k or last k triangles are nested.
Stated without proof in Lemma 2; this is the paper's weakest premise and the load-bearing geometric fact.
standard math The bounding box of a triangle has at least one corner that is a vertex of the triangle.
Used in Lemma 2 to show nested bounding boxes contribute points of U; proof is a brief pigeonhole argument.
domain assumption Uniform iid points in the unit square induce a uniform random permutation when sorted by x-coordinate.
Used in the proof of Theorem 1 to transfer the problem to Claim 3 about random permutations.
standard math Stirling's approximation: L! >= (L/e)^L.
Used in Claim 3 to bound the union bound probability.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs." pith.science (2026). https://pith.science/paper/ADBGHYG3

@misc{pith2026190807097,
  author       = {Pith},
  title        = {Pith review of: An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ADBGHYG3}},
  note         = {Machine review of arXiv:1908.07097}
}

abstract

A set $U\subseteq \reals^2$ is $n$-universal if all $n$-vertex planar graphs have a planar straight-line embedding into $U$. We prove that if $Q \subseteq \reals^2$ consists of points chosen randomly and uniformly from the unit square then $Q$ must have cardinality $\Omega(n^2)$ in order to be $n$-universal with high probability. This shows that the probabilistic method, at least in its basic form, cannot be used to establish an $o(n^2)$ upper bound on universal sets.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 8 canonical work pages

[1]

Bannister , Zhanpeng Cheng , William E

Michael J. Bannister , Zhanpeng Cheng , William E. Devanny , and David Eppstein . Superpatterns and universal point sets. Journal of Graph Algorithms and Applications , 18:177--209, 2014. http://dx.doi.org/10.7155/jgaa.00318 doi:10.7155/jgaa.00318

work page doi:10.7155/jgaa.00318 2014
[2]

Brandenburg

Franz J. Brandenburg. Drawing planar graphs on 8 9 n^2 area. Electronic Notes in Discrete Mathematics , 31:37 -- 40, 2008. The International Conference on Topological and Geometric Graph Theory. URL: http://www.sciencedirect.com/science/article/pii/S1571065308000619, http://dx.doi.org/https://doi.org/10.1016/j.endm.2008.06.005 doi:https://doi.org/10.1016/...

work page doi:10.1016/j.endm.2008.06.005 2008
[3]

On universal point sets for planar graphs

Jean Cardinal, Michael Hoffmann, and Vincent Kusters. On universal point sets for planar graphs. In Jin Akiyama, Mikio Kano, and Toshinori Sakai, editors, Computational Geometry and Graphs , pages 30--41, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. http://dx.doi.org/10.1007/978-3-642-45281-9_3 doi:10.1007/978-3-642-45281-9_3

work page doi:10.1007/978-3-642-45281-9_3 2013
[4]

Chrobak and H

M. Chrobak and H. Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News , 20, 1989

work page 1989
[5]

Chrobak and T.H

M. Chrobak and T.H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters , 54(4):241 -- 246, 1995. URL: http://www.sciencedirect.com/science/article/pii/002001909500020D, http://dx.doi.org/https://doi.org/10.1016/0020-0190(95)00020-D doi:https://doi.org/10.1016/0020-0190(95)00020-D

arXiv 1995
[6]

De Fraysseix, J

H. De Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica , 10(1):41--51, Mar 1990. URL: https://doi.org/10.1007/BF02122694, http://dx.doi.org/10.1007/BF02122694 doi:10.1007/BF02122694

doi:10.1007/bf02122694 1990
[7]

n straight line representation of planar graphs

Istv \'a n F \'a ry. n straight line representation of planar graphs. Acta Sci.Math. Szeged , 11:229--233, 1948

work page 1948
[8]

On the length of the longest monotone subsequence in a random permutation

Alan Frieze. On the length of the longest monotone subsequence in a random permutation. Ann. Appl. Probab. , 1(2):301--305, 05 1991. URL: https://doi.org/10.1214/aoap/1177005939, http://dx.doi.org/10.1214/aoap/1177005939 doi:10.1214/aoap/1177005939

arXiv 1991

Show all 12 references

[9]

A 1.235 lower bound on the number of points needed to draw all n -vertex planar graphs

Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all n -vertex planar graphs. Information Processing Letters , 92:95--98, oct 2004. http://dx.doi.org/10.1016/j.ipl.2004.06.009 doi:10.1016/j.ipl.2004.06.009

2004 doi
[10]

A note on universal point sets for planar graphs

Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner. A note on universal point sets for planar graphs. ArXiv , abs/1811.06482, 2018

2018 arXiv
[11]

Embedding planar graphs on the grid

Walter Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '90, pages 138--148, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=32...

1990
[12]

Congruent graphs and the connectivity of graphs

Hassler Whitney. Congruent graphs and the connectivity of graphs. Amer. J. Math. , 54:150--168, 1932

1932

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Bannister , Zhanpeng Cheng , William E

Michael J. Bannister , Zhanpeng Cheng , William E. Devanny , and David Eppstein . Superpatterns and universal point sets. Journal of Graph Algorithms and Applications , 18:177--209, 2014. http://dx.doi.org/10.7155/jgaa.00318 doi:10.7155/jgaa.00318

work page doi:10.7155/jgaa.00318 2014

[2] [2]

Brandenburg

Franz J. Brandenburg. Drawing planar graphs on 8 9 n^2 area. Electronic Notes in Discrete Mathematics , 31:37 -- 40, 2008. The International Conference on Topological and Geometric Graph Theory. URL: http://www.sciencedirect.com/science/article/pii/S1571065308000619, http://dx.doi.org/https://doi.org/10.1016/j.endm.2008.06.005 doi:https://doi.org/10.1016/...

work page doi:10.1016/j.endm.2008.06.005 2008

[3] [3]

On universal point sets for planar graphs

Jean Cardinal, Michael Hoffmann, and Vincent Kusters. On universal point sets for planar graphs. In Jin Akiyama, Mikio Kano, and Toshinori Sakai, editors, Computational Geometry and Graphs , pages 30--41, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. http://dx.doi.org/10.1007/978-3-642-45281-9_3 doi:10.1007/978-3-642-45281-9_3

work page doi:10.1007/978-3-642-45281-9_3 2013

[4] [4]

Chrobak and H

M. Chrobak and H. Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News , 20, 1989

work page 1989

[5] [5]

Chrobak and T.H

M. Chrobak and T.H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters , 54(4):241 -- 246, 1995. URL: http://www.sciencedirect.com/science/article/pii/002001909500020D, http://dx.doi.org/https://doi.org/10.1016/0020-0190(95)00020-D doi:https://doi.org/10.1016/0020-0190(95)00020-D

arXiv 1995

[6] [6]

De Fraysseix, J

H. De Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica , 10(1):41--51, Mar 1990. URL: https://doi.org/10.1007/BF02122694, http://dx.doi.org/10.1007/BF02122694 doi:10.1007/BF02122694

doi:10.1007/bf02122694 1990

[7] [7]

n straight line representation of planar graphs

Istv \'a n F \'a ry. n straight line representation of planar graphs. Acta Sci.Math. Szeged , 11:229--233, 1948

work page 1948

[8] [8]

On the length of the longest monotone subsequence in a random permutation

Alan Frieze. On the length of the longest monotone subsequence in a random permutation. Ann. Appl. Probab. , 1(2):301--305, 05 1991. URL: https://doi.org/10.1214/aoap/1177005939, http://dx.doi.org/10.1214/aoap/1177005939 doi:10.1214/aoap/1177005939

arXiv 1991