Introduction

Generating a random graph is easy if you ignore structure. Generating a large random planar graph is harder because every edge you add has to preserve the ability to draw the graph with no crossings.

What Makes a Graph Planar

A planar graph is one that can be embedded in the plane so that edges intersect only at shared endpoints. That definition adds a hard structural limit: for a simple connected planar graph with at least three vertices, the number of edges can never exceed 3n - 6.

That formula is useful as a sanity check. If you ask for 1000 vertices and 5000 edges, the request is already impossible because a simple planar graph of that size can have at most 2994 edges.

There are two different problems people mix together:

• generating some large planar graph with random-looking structure
• sampling uniformly from the space of all planar graphs of a given size

The second problem is research-grade and much harder. For many engineering tasks, the first problem is good enough.

A Practical Generation Strategy

A simple and effective approach is to start with a connected planar backbone and then add random candidate edges one at a time. After each addition, run a planarity test. If the edge keeps the graph planar, keep it. Otherwise, remove it and continue.

This does not produce a uniform distribution over all planar graphs, but it is easy to implement and works well when you want a large valid planar graph for testing or experimentation.

The example below uses networkx and its built-in planarity test.

1import itertools
2import random
3import networkx as nx
4
5
6def random_planar_graph(n, target_edges, seed=42):
7    if n < 1:
8        raise ValueError("n must be positive")
9
10    max_edges = 3 * n - 6 if n >= 3 else n * (n - 1) // 2
11    if target_edges > max_edges:
12        raise ValueError(f"target_edges must be at most {max_edges}")
13
14    rng = random.Random(seed)
15    graph = nx.Graph()
16    graph.add_nodes_from(range(n))
17
18    # Start with a random tree so the graph is connected and planar.
19    for node in range(1, n):
20        parent = rng.randrange(node)
21        graph.add_edge(node, parent)
22
23    candidates = list(itertools.combinations(range(n), 2))
24    rng.shuffle(candidates)
25
26    for u, v in candidates:
27        if graph.number_of_edges() >= target_edges:
28            break
29        if graph.has_edge(u, v):
30            continue
31
32        graph.add_edge(u, v)
33        is_planar, _ = nx.check_planarity(graph)
34        if not is_planar:
35            graph.remove_edge(u, v)
36
37    return graph
38
39
40g = random_planar_graph(n=30, target_edges=50, seed=7)
41print(g.number_of_nodes(), g.number_of_edges())
42print(nx.check_planarity(g)[0])

This generator does three useful things. It guarantees connectivity by starting from a random tree, it rejects non-planar additions immediately, and it lets you control density with target_edges.

Scaling the Approach

For moderate graph sizes, repeated planarity checks are often good enough. For very large graphs, though, the naive add-and-test loop can become a bottleneck.

A few ways to improve it:

• stop near the density you actually need instead of chasing the maximum edge count
• bias candidate edges toward nearby vertices if a geometric feel is acceptable
• build from planar primitives such as triangulations and then remove random edges
• store the resulting embedding if later algorithms need face information

If you need a graph that is both large and geometry-aware, another practical route is to generate random points in the plane and compute a planar proximity structure such as a Delaunay triangulation, then remove edges randomly. That gives you a planar graph with a more natural spatial interpretation.

The right method depends on what random means for your use case. A benchmark graph, a game map, and a graph theory experiment may all need different kinds of randomness.

Common Pitfalls

• Requesting more than 3n - 6 edges for a simple planar graph. The generator cannot satisfy an impossible target.
• Assuming random edge addition with rejection gives a uniform random planar graph. It does not.
• Forgetting to ensure connectivity if your application expects one connected component.
• Running a full planarity check after every edge on extremely large graphs without considering performance.
• Confusing a geometric graph with a planar graph. A graph can be planar without already having coordinates attached to its vertices.

Summary

• Planar graph generation is constrained by structure, not just by random edge choice.
• A simple practical generator starts from a tree and adds random edges while rejecting anything non-planar.
• '3n - 6 is the key upper bound for simple connected planar graphs with at least three vertices.'
• Repeated planarity checks are fine for many workloads, but truly uniform sampling is a much harder problem.
• Choose a generation strategy that matches whether you need connectivity, density control, geometry, or statistical rigor.