Random Plane Graphs 2026
This 2026 Polymath Jr project will be run by Adam Sheffer. It involves a mix of graph theory and probability.
Plane graphs.
Let P be a set of points in the plane. A plane graph of P is a graph with a vertex for every point of P. Unlike general graphs, we are not allowed to move the vertices of a plane graph. The edge are non-crossing and straight.
This type of graphs arose from the field of Computational Geometry (part of computer science), since it models many real-world situations.
You may be familiar with planar graphs. If so, note that every plane graph is also a planar graph. However, a planar graph may not be plane of a given point set. For example, all three graphs in the figure above are planar, but only one is plane.
Numbers of plane graphs.
For most point sets P, we can draw many different plane graphs on P. For example, the following figure depicts six different plane graphs that can be drawn on a specific set of five points (many other plane graphs can be drawn on these five points).
There has been significant interest in finding the maximum number of plane graphs that can be drawn on a set of n points, for large n. For example, we know that n points on a circle have about 11.65ⁿ plane graphs that can be drawn on them. See below to the left. The current world-record is the configuration below to the right, with about 42.11ⁿ plane graphs.
The trickier part is to prove that every n points have at most some number of plane graphs. The current best bound states that every n points have at most 187.53ⁿ plane graphs. There remains quite a wide gap between this bound and the configuration with 42.11ⁿ plane graphs.
Many variants of this problem have been studied. For example: What is the minimum number of plane graphs that n points may have. What is the maximum number of plane spanning trees that n points may have? Plane spanning cycles? For some of the current results, click here.
Random plane graphs.
In a random graph, we choose each potential edge with some probability p. The study of random graphs is a successful field with a rich history and many applications. Many books have been written about the subject. However, all known techniques break down when discussing a random plane graph.
When dealing with plane graphs, we cannot take each edge with some probability p, since this may lead to edge crossings. For example, consider keeping each edge in the following graph with some probability.
Instead, we define a random plane graph of a point set P as a graph uniformly chosen from the set of all plane graphs of P. For example, for three points not all on the same line, each of the following graphs is obtained with probability 1/8.
This alternative definition of random graphs is much more difficult to study. For example, it is easy to find the expected degree of a vertex in a standard random graph. It is not known how to do so for a random plane graph.
Beyond the intrinsic interest in understanding random plane graphs, they are also quite useful. Remember the above statement about every n points having at most 187.53ⁿ plane graphs? This is a direct consequence of proving that the expected number of isolated vertices in a random plane graph is at least n/187.53. Want to learn more? Join the project!
In this project. We will study random plane graphs and try to derive new properties of those. For example, new properties of vertex degrees in a random plane graph. We may also consider random plane spanning cycles, random plane spanning trees, and other types of plane graphs.
