# 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 triangulations Eulerian triangulations planar simple graphs planar simple bipartite graphs triangulations of a disk simple quadrangulations Apollonian networks Number $n$ of vertices (max. 20) Connectivity $\geq$ 1 1, but not 2 2 2, but not 3 3 4 Minimum degree $\geq$ 1 2 3 4 5 Connectivity and degrees 3-connected 3-connected + min-degree 5 5-connected 4-connected + min-degree 5 3-connected + separating 3-cycle + min-degree 5 4-connected + separating 4-cycle + min-degree 5 3-connected + min-degree 4 4-connected 3-connected + separating 3-cycle + min-degree 4 2-connected + min-degree 3 2-connected + min-degree 3 + parallel edges 1-connected + min-degree 3 + no faces share more than one edge 1-connected + min-degree 3 + no faces share more than one edge + loop 1-connected + min-degree 3 1-connected + min-degree 3 + loop 3-connected 4-connected 3-connected + separating 3-cycle no chords + no degree-2 vertices chords allowed + no degree-2 vertices chords required + not degree-2 vertices chords allowed + degree-2 vertices allowed chords required + degree-2 vertices allowed 3-connected arbitrary min-degree 3 3-connected, no non-facial 4-cycles Minimum number of edges Maximum number of edges Maximum face size Outer face size Forbid reversal Write duals Graph format graph6 sparse6 edge list adjacency list (cw) adjacency matrix Output format text (≤10000 objects) file (≤100000 objects)
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:
• 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