OEIS A005470 · A003094 · A021103
A graph is planar when it can be drawn in the plane with no two edges crossing. Below is every planar graph on up to 7 vertices, each one taken apart into the pieces it is built from. The same pieces, assembled in reverse, count the planar graphs on 25 vertices without drawing a single one.
Until now these counts were known to 15 vertices, found by generating every graph. The terms from 16 to 25 are new.
Edge color shows how well connected a graph is. Pick any graph to take it apart.
How the count works
The inspector above takes a graph apart: into connected components, then into blocks at the cut vertices, then into cycles, bundles and 3-connected pieces along pairs of vertices whose removal would split it (the SPQR tree). The count runs the same steps in the other direction. It is a sum over shapes, never a list of graphs, so the work grows with the number of vertices, not with the number of graphs.
The hard part is symmetry. Graphs are counted up to relabeling, so a symmetric graph must not be counted once for each of its mirror images. Every step therefore carries a cycle index: a record of how each symmetry permutes vertices and edges, from which Pólya's method removes the duplicates.
All arithmetic is done modulo several primes below 224 and recombined by the Chinese remainder theorem; the largest convolutions in step 1 run on a GPU. The method reproduces every previously known term (n ≤ 15, and n ≤ 14 for 2-connected graphs), and the gallery's class counts for n ≤ 7 agree with it graph by graph.
The numbers
Number of graphs on n vertices, logarithmic scale. Hollow points are new.
Share of the planar graphs on n vertices in each class. 3-connected graphs (polyhedra) become a thin sliver.
Ratio a(n)/a(n−1) for all planar graphs. The ratio tends to a growth constant γ that is not known exactly. It is at least 27.2269, the growth constant of labeled planar graphs (Giménez and Noy, 2009), and at most 24.91 ≈ 30.06 (Bonichon, Gavoille and Hanusse). At n = 25 the ratio is still well below the band.