The Combinatorial Object Server

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

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.

OEIS sequences related to $n$-vertex planar graphs:

- Triangulations – 3-connected: OEIS A000109
- Triangulations – 3-connected (forbid reversal): OEIS A253882
- Triangulations – 3-connected + min-degree 4: OEIS A000103
- Triangulations – 4-connected: OEIS A007021
- Triangulations – min-degree 5: OEIS A081621
- Eulerian triangulations – 3-connected: OEIS A007083
- Eulerian triangulations – 4-connected: OEIS A171090
- Planar simple graphs – 3-connected: OEIS A000944
- Planar simple graphs – 3-connected (forbid reversal): OEIS A119501
- Planar simple graphs – 3-connected + min-degree 4: OEIS A007025
- Planar simple graphs – 3-connected + min-degree 5: OEIS A049373
- Planar simple bipartite graphs – 3-connected: OEIS A007028
- Triangulations of a disk – outer face size 3 + no chords + no degree-2 vertices: OEIS A002713
- Triangulations of a disk – outer face size 4 + no chords + no degree-2 vertices: OEIS A058786
- Quadrangulations – arbitrary: OEIS A113201
- Quadrangulations – arbitrary (forbid reversal): OEIS A113202
- Quadrangulations – 3-connected: OEIS A007022
- Quadrangulations – 3-connected (forbid reversal): OEIS A113204
- Quadrangulations – 3-connected + no non-facial 4-cycles: OEIS A002880
- Quadrangulations – 3-connected + no non-facial 4-cycles (forbid reversal): OEIS A113205
- Quadrangulations – min-degree 3: OEIS A078666
- Quadrangulations – min-degree 3 (forbid reversal): OEIS A113203
- Apollonian networks: OEIS A027610
- Apollonian networks (forbid reversal): OEIS A007173

- [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.