Generate plane triangulations and quadrangulations
Generate various types of plane graphs.
This is a website interface to the program plantri, written by Gunnar Brinkmann and Brendan McKay.
The default graph format are adjacency lists, where the neighbors of each vertex are listed in clockwise (cw) order around the vertex in the embedding of the graph.
Some other graph formats are also available (graph6, sparse6, etc.), but these other formats do not encode the embedding.
Object type
Number $n$ of vertices
(max. 20)
Connectivity $\geq$
Minimum degree $\geq$
Connectivity and degrees
Minimum number of edges
Maximum number of edges
Maximum face size
Outer face size
Forbid reversal
Write duals
Graph format
Output format
Output
numbering
graphics
Object info
A plane graph is a graph embedded in the plane such that no two edges cross, and a graph is called planar if it can be realized as a plane graph.
If a planar graph is 3-connected, then its embedding into the plane is unique, so in this case the distinction between plane and planar graphs is irrelevant.
A triangulation is a plane graph in which every face is a triangle.
Similarly, a quadrangulation is a plane graph in which every face has length 4.
A Eulerian graph is a connected graph where all vertices have even degree.
A triangulation of a disk is a plane graph with a distinguished outer face, which can have any size, and all other faces must be triangles.
The size of the outer face can be specified in the input.
If this size is not specified, then all possible outer face sizes are generated.
An Apollonian network is a plane triangulation that can be formed by starting with the complete graph on 4 vertices, and then repeatedly dividing a face into three by the addition of a new vertex.
The dual of a plane graph is the graph obtained by placing a vertex into every face, and by connecting any two such vertices in faces that share an edge through this edge.
For example, consider the plane triangulation (the octahedron) and its dual quadrangulation (the cube) shown in black and red below, respectively.
A plane graph can be represented uniquely by adjacency lists, where the neighbors of each vertex are listed in clockwise (cw) order around that vertex in the embedding.
The adjacency list representation of the black graph above is 1[2 4 6 3] 2[1 3 5 4] 3[1 6 5 2] 4[1 2 5 6] 5[2 3 6 4] 6[1 4 5 3], and that of its dual in red is 1[2 8 3] 2[1 4 5] 3[1 7 4] 4[2 3 6] 5[2 6 8] 6[4 7 5] 7[3 8 6] 8[1 5 7].
When deciding isomorphism between plane graphs, one can either allow turning the graph upside down (reversing the orientation of the outer face), or equivalently, reverse the orientation of all adjacency lists, or one can forbid this operation, yielding possibly more non-isomorphic graphs.
As only adjacency lists allow reconstructing the embedding, this option is only available for this output format.
Enumeration (OEIS)
OEIS sequences related to $n$-vertex planar graphs:
[BGG+05] G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas, and P. Wollan. Generation of simple quadrangulations of the sphere. Discrete Math., 305(1-3):33–54, 2005.
[BM05] G. Brinkmann and B. D. McKay. Construction of planar triangulations with minimum degree 5. Discrete Math., 301(2-3):147–163, 2005.
[BM07] G. Brinkmann and B. D. McKay. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem., 58(2):323–357, 2007.