Graph / Triangulation (Bibtex)

P394: Enumeration of all triangulations of 2-sphere

Input:

A 2-sphere $G$.

Output:

All triangulations of $G$.

Complexity:

Comment:

Reference:

[Bowen1967a] (Bibtex)

P320: Enumeration of all $r$-rooted $2$-connected triangulations of a planar graph

Input:

A planar graph $G = (V, E)$ and an integer $r$.

Output:

All $r$-rooted $2$-connected triangulations of $G$.

Complexity:

$O(|V|^2N)$ total time and $O(|V|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Avis1996b] (Bibtex)

P321: Enumeration of all $r$-rooted $3$-connected triangulations of a planar graph

Input:

A planar graph $G = (V, E)$ and an integer $r$.

Output:

All $r$-rooted $3$-connected triangulations of $G$.

Complexity:

$O(|V|^2N)$ total time and $O(|V|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Avis1996b] (Bibtex)

P144: Enumeration of all based plane triangulations with $n$ vertices

Input:

An integer $n$.

Output:

All based plane triangulations.

Complexity:

$O(1)$ time per based plane triangulation with $O(n)$ space.

Comment:

A \textit{based plane triangulation} is a plane triangulation with one designated edge on the outer face. The algorithm does not output entire solution but output the difference from the previous solution.

Reference:

[Nakano2004a] (Bibtex)

P145: Enumeration of all biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face

Input:

Integers $n$ and $r$.

Output:

All biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face.

Complexity:

$O(1)$ time per based plane triangulation with $O(n)$ space.

Comment:

A \textit{based plane triangulation} is a plane triangulation with one designated edge on the outer face. The algorithm does not output entire solution but output the difference from the previous solution.

Reference:

[Nakano2004a] (Bibtex)

P146: Enumeration of all biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer face

Input:

Integers $n$ and $r$.

Output:

All biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face.

Complexity:

$O(r^2n)$ time per based plane triangulation with $O(n)$ space.

Comment:

Reference:

[Nakano2004a] (Bibtex)

P160: Enumeration of all rooted triconnected plane triangulations with at most $n$ vertices

Input:

An integer $n$.

Output:

All triconnected rooted plane triangulations with at most $n$ vertices.

Complexity:

$O(1)$ time per tree and $O(n)$ space.

Comment:

A \textit{rooted} plane triangulation is a plane triangulation with one designated vertex on the outer face.

Reference:

[Nakano2001] (Bibtex)

P161: Enumeration of all rooted triconnected plane triangulations with exactly $n$ vertices and $r$ leaves

Input:

An integer $n$.

Output:

All triconnected rooted plane triangulations with exactly $n$ vertices and $r$ leaves.

Complexity:

$O(r)$ time per tree and $O(n)$ space.

Comment:

A \textit{rooted} plane triangulation is a plane triangulation with one designated vertex on the outer face.

Reference:

[Nakano2001] (Bibtex)

P162: Enumeration of all triconnected plane triangulations with exactly $n$ vertices and $r$ leaves

Input:

An integer $n$.

Output:

All triconnected plane triangulations with exactly $n$ vertices and $r$ leaves.

Complexity:

$O(r^n)$ time per triangulation and $O(n)$ space.

Comment:

Reference:

[Nakano2001] (Bibtex)

P170: Enumeration of all biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer faces

Input:

Integers $n$ and $r$.

Output:

All biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer faces.

Complexity:

$O(rn)$ time per triangulation and $O(n)$ space.

Comment:

Reference:

[Nakano2004b] (Bibtex)

P173: Enumeration of all triangulations of a triconnected plane graph of $n$ vertices

Input:

A triconnected planar graph $G$ with $n$ vertices.

Output:

All triangulations of $G$.

Complexity:

$O(1)$ time per triangulation and $O(n)$ space.

Comment:

Reference:

[Parvez2009] (Bibtex)