Keywords

1 Introduction and Overview

An lists all the solutions of a problem, without duplicates, and then stops. Its efficiency is measured in terms of setup time, space usage, and between the outputs of two consecutive solutions; see, e.g., [3, 42, 50, 58]. In this paper, we present efficient algorithms to enumerate: (i) straight-line grid drawings produced with the algorithms by de Fraysseix, Pach, and Pollack [25, 26] ( ) and by Schnyder [52] ( ), and (ii) the corresponding combinatorial structures. To the best of our knowledge, these are the first enumeration algorithms for drawings of graphs.

Notable applications of graph drawing enumeration algorithms include:

  1. (1)

    Users can benefit from having multiple alternative drawings that highlight different features of the graph, enabling them to choose the most suitable for their specific needs; this strategy has been used already in [8].

  2. (2)

    Machine-learning-based graph drawing tools profit from multiple drawings of a graph; small-delay enumeration algorithms may fuel the training process of these tools.

  3. (3)

    Computer-aided systems that aim to verify geometric and topological statements can leverage enumeration algorithms to explore the solution space of graph drawing problems.

Preliminary Definitions. We consider graphs and digraphs with multiple edges. A is a planar graph without parallel edges to which no edge can be added without losing planarity or simplicity. A is a planar graph with a prescribed embedding.

Fig. 1.
figure 1

(a), (b) The two canonical orderings with first vertex u of a maximal planar graph G. (c) The unique canonical orientation with first vertex u of G. (d) The unique Schnyder wood of G.

Full size image

Let G be a maximal plane graph and let (u, v, z) be the cycle delimiting its outer face, where u, v, and z appear in this counter-clockwise order along the cycle. A is a labeling of the vertices \(v_1=u, v_2=v, v_3, \dots , v_{n-1}, v_n=z\) such that, for every \(3 \le k \le n-1\) (see Figs. 1(a), 1(b), and [26]):

(CO-1):

The plane subgraph \(G_{k} \subseteq G\) induced by \(v_1,v_2,\dots ,v_k\) is 2-connected; let \(C_k\) be the cycle bounding its outer face;

(CO-2):

\(v_{k+1}\) is in the outer face of \(G_{k}\), and its neighbors in \(G_{k}\) form an (at least 2-element) subinterval of the path \(C_{k}-(u,v)\).

A of G is a canonical ordering of G with first vertex x, where \(x\in \{u,v,z\}\). If \(G'\) is a maximal planar graph, a of \(G'\) is a canonical ordering of a maximal plane graph isomorphic to \(G'\). Let \(\pi =(v_1,\dots ,v_n)\) be a canonical ordering of G with first vertex \(v_1\). Orient every edge \((v_i,v_j)\) of G from \(v_i\) to \(v_j\) if and only if \(i<j\). The resulting orientation is the . An orientation \(\mathcal D\) of G is a if there exists a canonical ordering \(\pi \) of G with first vertex u such that \(\mathcal D\) is the canonical orientation of G with respect to \(\pi \); see Fig. 1(c). A of G is a canonical orientation with first vertex x, where x is a vertex in \(\{u,v,z\}\). Finally, if \(G'\) is a maximal planar graph, a of \(G'\) is a canonical orientation of a maximal plane graph isomorphic to \(G'\).

A vertex or edge of G is if it is not incident to the outer face and otherwise. A of G is an assignment of directions and of the colors 1, 2 and 3 to the internal edges of G such that (see Fig. 2 and [52]):

(S-1):

For \(i=1,2,3\), each internal vertex x has one outgoing edge \(e_i\) of color i. The outgoing edges \(e_1\), \(e_2\), and \(e_3\) appear in this counter-clockwise order at x. Further, for \(i=1,2,3\), all the incoming edges at x of color i appear in the clockwise sector between \(e_{i+1}\) and \(e_{i-1}\), where \(i+1=1\) if \(i=3\) and \(i-1 = 3\) if \(i=1\).

(S-2):

At the outer vertices u, v, and z, all the internal edges are incoming and of color 1, 2, and 3, respectively. If \(G'\) is a maximal planar graph, a of \(G'\) is a Schnyder wood of a maximal plane graph isomorphic to \(G'\).

Fig. 2.
figure 2

Illustration for the properties of a Schnyder wood.

Full size image

Our Contributions. First, we present an algorithm that enumerates all canonical orientations of an n-vertex maximal plane graph G by applying edge contraction or removals. This results in smaller graphs, whose canonical orientations are recursively enumerated and modified to obtain canonical orientations of G by orienting the contracted or removed edges. To achieve polynomial delay, contractions and removals should be applied only if the corresponding branch of computation produces at least one canonical orientation of G. We determine necessary and sufficient conditions for a subgraph of G to allow for an orientation that can be extended to a canonical orientation of G. We establish topological properties that determine whether applying a contraction or a removal results in a graph satisfying these conditions. Additionally, we create efficient data structures for testing and applying the operations based on these properties.

Second, we prove that canonical orderings are topological sortings of canonical orientations. This allows our algorithm for enumerating the former to be used for enumerating the latter. Moreover, since canonical orientations are in correspondence with Schnyder woods [22, Theorem 3.3], our algorithm for enumerating canonical orientations can also be used to enumerate all Schnyder woods of G.

Third, we show that applying the FPP-algorithm with different canonical orderings corresponding to the same canonical orientation yields the same drawing of G. This establishes a correspondence between the canonical orientations of G and the drawings produced by the FPP-algorithm. Together with our algorithm for enumerating canonical orientations, this allows us to enumerate such drawings.

Finally, we show that the drawings generated by the S-algorithm are in bijection with the Schnyder woods. This, the bijection between canonical orientations and Schnyder woods, and our algorithm for enumerating canonical orientations enable us to enumerate the drawings of G produced by the S-algorithm.

All our enumeration algorithms have \(\mathcal {O}(n)\) setup time, space usage, and worst-case delay.

Related Results. The planar straight-line drawings of maximal planar graphs generated by the FPP-algorithm [25, 26] and by the S-algorithm [52] are fundamental in graph drawing [28, 45, 57] and find applications in other fields, e.g., knot theory [15, 36, 37] and computational complexity [7, 34, 51]. Further, the combinatorial structures conceived for these algorithms, i.e., canonical orderings and Schynder woods, are used for a plethora of problems in graph drawing [1, 2, 4, 20, 23, 27, 30, 31, 33, 41, 46] and beyond [5, 11,12,13, 18, 38, 39]. Canonical orderings and Schnyder woods appear to be distant concepts. However, Schnyder [52] has shown how to get a Schnyder wood from a canonical ordering. Also, their relationship is explained by the concept of canonical orientations, which in [22] are proved to be in bijection with the Schnyder woods; see also [44].

While enumerating graph drawings is a novel subject, the enumeration of graph orientations has a rich literature. The enumeration of acyclic orientations and k-arc-connected orientations are studied in [6, 19, 55] and [10], respectively. An of a graph G is an acyclic orientation of G such that s and t are its unique source and sink, respectively. In [24] a polynomial-delay algorithm is provided for enumerating st-orientations. In [53], the algorithm in [24] is refined to obtain linear delay, if the input is biconnected and planar. Our paper is connected to these algorithms through a result by de Fraysseix and Ossona de Mendez [22]: There is a bijection between the canonical orientations and the bipolar orientations such that every internal vertex has at least two incoming edges. Our enumeration algorithm for canonical orientations follows the strategy of [24, 53] for enumerating bipolar orientations of biconnected planar graphs. However, requiring that every internal vertex has at least two incoming edges dramatically increases the complexity of the problem and reveals new and, in our opinion, interesting topological properties of the desired orientations.

The canonical orientations of a maximal plane graph form a distributive lattice \(\mathcal L\) [32]. By the fundamental theorem of finite distributive lattices [9], there is a finite poset P whose order ideals correspond to the elements of \(\mathcal L\) and it is known that |P| is polynomial in n [32, page 10]. Enumerating the order ideals of P is a studied problem. In [35] an algorithm is presented that lists all order ideals of P in \(\mathcal {O}(\varDelta (P))\) delay, where \(\varDelta (P)\) is the maximum indegree of the covering graph of P. However, the algorithm has three drawbacks that make it unsuitable for solving our problems. First, the guaranteed delay of the algorithm is amortized, and not worst-case. Second, the algorithm uses \(\mathcal {O}(w(P)\cdot |P|) = \mathcal {O}(n^3)\) space, where \(w(P)=\mathcal {O}(n)\) is the width of P, and \(\mathcal {O}(|P|^2) = \mathcal {O}(n^4)\) preprocessing time. Third and most importantly, each order ideal is produced twice by the algorithm, rather than just once as required by an enumeration algorithm. Similarly, the algorithms in [48, 54, 56] are affected by all or by part of the above drawbacks.

Open Problems. Our research sparkles new questions. In general, for a graph G and a drawing style \(\mathcal D\), we may ask for algorithms to enumerate the drawings of G respecting \(\mathcal D\). Examples include: (i) enumerating the planar straight-line drawings of a planar graph on a given grid; (ii) enumerating the orthogonal representations of a plane graph with at most b bends; and (iii) enumerating the upward planar embeddings of a single-source or triconnected DAG.

Full details of omitted or sketched proofs can be found in the full version of the paper [21].

2 Canonical Orientations

In [22, Lemma 3.6–3.7, Theorem 3.3], the following characterization has been shown, for which we provide an alternative proof in the full version of the paper.

Theorem 1

([22]). Let G be an n-vertex maximal plane graph and let (u, v, z) be the cycle delimiting its outer face, where u, v, and z appear in this counter-clockwise order along the cycle. An orientation \(\mathcal D\) of G is a canonical orientation with first vertex u if and only if \(\mathcal D\) is a uz-orientation in which every internal vertex has at least two incoming edges.

Our proof of Theorem 1 also implies the following.

Lemma 1

Any topological sorting of a canonical orientation with first vertex u of a maximal plane graph G is a canonical ordering of G with first vertex u.

Let \(h_1\) and \(h_2\) be parallel edges in a plane graph. We denote by \(\ell (h_1,h_2)\) the open region bounded by \(h_1\) and \(h_2\), and say that \(\ell (h_1,h_2)\) is a if it contains no vertices in its interior. Note that \(\ell (h_1,h_2)\) might contain edges parallel to \(h_1\) and \(h_2\) in its interior, or it might coincide with an internal face of the graph; see Fig. 3. We now provide some crucial definitions.

Fig. 3.
figure 3

Any two of the edges \(r_1\), \(r_2\), and \(r_3\) form a multilens, the edges \(b_2\) and \(b_3\) form a multilens, whereas neither \(b_2\) nor \(b_3\) forms a multilens with \(b_1\); the multilenses \(\ell (r_1,r_2)\), \(\ell (r_2,r_3)\), and \(\ell (b_2,b_3)\) are also faces.

Full size image

Definition 1

A biconnected plane graph G with two distinguished vertices s and t is called if it satisfies the following conditions (refer to Fig. 3):

  1. (1)

    s and t (which are called the of G) are incident to the outer face of G and s immediately precedes t in clockwise order along the cycle \(C_o\) bounding such a face;

  2. (2)

    all the internal faces of G have either two or three incident vertices;

  3. (3)

    multiple edges, if any, are all incident to s; and

  4. (4)

    if two parallel edges \(h_1\) and \(h_2\) with end-vertices s and x exist such that \(\ell (h_1,h_2)\) is not a multilens, then two parallel edges \(h'_1\) and \(h'_2\) between s and a vertex \(y\ne x\) exist such that \(\ell (h'_1,h'_2)\) is a multilens and such that \(\ell (h'_1,h'_2)\subset \ell (h_1,h_2)\).

Definition 2

An st-orientation \(\mathcal D\) of a well-formed biconnected plane graph G with poles s and t is if every internal vertex has at least two incoming edges in \(\mathcal D\).

Definition 3

Let G be a plane graph. The an edge \(e=(u,v)\) removes e from G and “merges” u and v into a new vertex w. Let \(e, e^u_1,\dots ,e^u_h\) and \(e,e^v_1,\dots ,e^v_k\) be the clockwise order of the edges incident to u and to v, respectively. Then the clockwise order of the edges incident to w is \(e^u_1,\dots ,e^u_h, e^v_1,\dots ,e^v_k\).

Note that the contraction of an edge may introduce parallel edges or self-loops.

Let G be a well-formed biconnected plane graph with poles s and t. Let \(e_1,e_2,\dots ,e_m\) be the counter-clockwise order of the edges incident to s, where \(e_1\) and \(e_m\) are the rightmost and leftmost edge incident to s, respectively, and let \(v_1,\dots ,v_m\) be the end-vertices of \(e_1,\dots ,e_m\) different from s, respectively. Moreover, let \(G^*\) be the plane multigraph resulting from the contraction of \(e_1\) in G; see Fig. 4(a). Also, if G contains parallel edges, let \(j\in \{1,\dots ,m-1\}\) be the smallest index such that \(e_{j}\) and \(e_{j+1}\) define a multilens of G; denote by \(G^-\) the plane graph resulting from the removal of \(e_1,\dots ,e_j\) from G; see Fig. 4(b). The next lemmas prove that, under certain conditions, \(G^*\) and \(G^-\) are well-formed multigraphs and can be used to obtain inner-canonical orientations of G.

Fig. 4.
figure 4

Illustration for the contraction of \(e_1\) (a) and the removal of \(e_1,\dots ,e_j\) (b).

Full size image

Lemma 2

Suppose that G does not contain parallel edges between s and \(w_1\), where \(w_1\) is the vertex that follows s in counter-clockwise direction along the outer face of G. Then \(G^*\) is a well-formed biconnected plane graph with poles s and t. Also, let \(\mathcal D^*\) be an inner-canonical orientation of \(G^*\). The orientation \(\mathcal D\) of G obtained from \(\mathcal D^*\) by orienting the edge \((s,w_1)\) away from s and by keeping the orientation of all other edges unchanged is inner-canonical.

Lemma 3

Suppose that G contains parallel edges and let \(j\in \{1,\dots ,m-1\}\) be the smallest index such that \(e_{j}\) and \(e_{j+1}\) define a multilens of G. Suppose also that either \(j=1\), or \(j>1\) and \(v_2,\dots ,v_j\) are not incident to the outer face of G. Then the graph \(G^-\) is a well-formed biconnected plane graph with poles s and t. Also, let \(\mathcal D^-\) be an inner-canonical orientation of \(G^-\). The orientation \(\mathcal D\) of G obtained from \(\mathcal D^-\) by orienting the edges \(e_1,e_2,\dots ,e_j\) away from s and by keeping the orientation of all other edges unchanged is inner-canonical.

By induction on |E(G)| and using Lemmas 2 and 3 we can prove the following.

Lemma 4

Every well-formed biconnected plane graph G with poles s and t has at least one inner-canonical orientation.

Section 2.1 is devoted to the proof of the following main result.

Theorem 2

Let G be a well-formed biconnected plane graph with \(\varphi \) edges. There is an algorithm with \(\mathcal {O}(\varphi )\) setup time and space usage listing all the inner-canonical orientations of G with \(\mathcal {O}(\varphi )\) delay.

Provided that Theorem 2 holds, we can prove the following.

Lemma 5

Let G be an n-vertex maximal plane graph and (u, v, z) be the cycle delimiting its outer face \(f_o\), where u, v, and z appear in this counter-clockwise order along \(f_o\). There is an algorithm with \(\mathcal {O}(n)\) setup time and space usage listing all the canonical orientations of G with first vertex u with \(\mathcal {O}(n)\) delay.

Proof (sketch):

We have that G is a well-formed biconnected plane graph with poles u and z. By Theorem 1, any canonical orientation of G with first vertex u is a uz-orientation such that every internal vertex has at least two incoming edges, i.e., an inner-canonical orientation. Also, any inner-canonical orientation of G is canonical. This, combined with G having \(\mathcal {O}(n)\) edges, implies that the algorithm in Theorem 2 enumerates all canonical orientations of G within the stated bounds.   \(\square \)

Theorem 3

There is an algorithm \(\mathcal {A}_1\) (resp. \(\mathcal {A}_2\)) with \(\mathcal {O}(n)\) setup time and space usage listing all canonical orientations of an n-vertex maximal plane (planar) graph with \(\mathcal {O}(n)\) delay.

Proof (sketch):

Algorithm \(\mathcal {A}_1\) uses the algorithm for the proof of Lemma 5 three times, i.e., once for each choice of the first vertex among the three vertices incident to the outer face of the input graph G. Algorithm \(\mathcal {A}_2\) applies \(4n-8\) times algorithm \(\mathcal {A}_1\), since there are \(4n-8\) maximal plane graphs that are isomorphic to G.    \(\square \)

2.1 The Inner-Canonical Enumerator Algorithm

We now describe the Inner-Canonical Enumerator (ICE) algorithm that enumerates all the inner-canonical orientations of a well-formed biconnected plane graph G with poles s and t (see Theorem 2). In the full version of the paper [21], we provide implementation details, data structures, and pseudocode for achieving the claimed worst-case bounds.

The ICE algorithm works recursively as follows. In the base case, G is the single edge \(e_m=(s,t)\), and its unique inner-canonical orientation is the one with the edge \(e_m\) directed from s to t. Otherwise, the algorithm considers four cases.

In Cases 1 and 2, G contains parallel edges and \(e_1\) is the unique edge between s and \(w_1\). Let \(j\in \{2,\dots ,m-1\}\) be the smallest index such that \(e_{j}\) and \(e_{j+1}\) define a multilens of G. In Case 1, there exists an index \(i\in \{2,\dots ,j\}\) such that \(v_i\) is incident to the outer face of G, while in Case 2 such an index does not exist. In Case 3, G does not contain parallel edges. Finally, in Case 4, G contains parallel edges between s and \(w_1\). Note that exactly one of Cases 1–4 applies to G.

In Cases 1 and 3, we contract the edge \((s,w_1)\). Let \(G^*\) be the resulting plane graph which, by Lemma 2, is biconnected and well-formed. Thus, the algorithm can be applied recursively to enumerate all inner-canonical orientations of \(G^*\). The algorithm obtains all inner-canonical orientations of G from the ones of \(G^*\) as in Lemma 2.

In Case 4, we remove the edges \(e_1,e_2,\dots ,e_j\). Let \(G'\) be the resulting plane graph which, by Lemma 3, is biconnected and well-formed. Thus, the algorithm can be applied recursively in order to enumerate all inner-canonical orientations of \(G'\). The algorithm obtains all inner-canonical orientations of G from the ones of \(G'\) as in Lemma 3.

In Case 2, the algorithm branches and applies both the contraction and the removal operations. Precisely, first we contract the edge \((s,w_1)\), obtaining a well-formed biconnected plane graph \(G^*\). After all inner-canonical orientations of \(G^*\) have been used to produce inner-canonical orientations of G as in Lemma 2, we remove the edges \(e_1,e_2,\dots ,e_j\) from G, obtaining a well-formed biconnected plane graph \(G'\), from which the remaining inner-canonical orientations of G are produced as in Lemma 3.

Note that the ICE algorithm outputs an inner-canonical orientation each time the base case applies. The next lemma summarizes its correctness.

Lemma 6

The ICE algorithm outputs all and only the inner-canonical orientations of G without repetitions.

3 Enumeration of Canonical Orderings and Drawings

We show how to efficiently enumerate the canonical orderings and drawings of a maximal plane or planar graph G. By Theorem 3, the canonical orientations of G can be generated efficiently. By Lemma 1, for every canonical orientation \(\mathcal D\) of G, the canonical orderings \(\pi \) of G such that \(\mathcal D\) is the canonical orientation of G with respect to \(\pi \) are the topological sortings of \(\mathcal D\). Since there exist \(\mathcal {O}(1)\)-delay algorithms [47, 49] for listing all such topological sortings, we get the following.

Theorem 4

There is an algorithm with \(\mathcal {O}(n)\) setup time and space usage listing all canonical orderings of an n-vertex maximal plane/planar graph with \(\mathcal {O}(n)\) delay.

Fig. 5.
figure 5

Illustrations for the FPP-algorithm. (a) \(\varGamma _k\). (b) \(\varGamma _{k+1}\).

Full size image

We show how to enumerate the planar straight-line drawings produced by the  [26]. Its input is an n-vertex maximal plane graph G, whose outer face is delimited by a cycle (u, v, z) and a canonical ordering \(\pi =(v_1=u,v_2=v,v_3,\dots ,v_n=z)\) of G. The FPP-algorithm works in steps.

The first step constructs a planar straight-line drawing \(\varGamma _3\) of \(G_3\) with \(v_1\), \(v_2\), and \(v_3\) at (0, 0), (2, 0), and (1, 1), respectively, and defines sets \(M_3(v_1)=\{v_1,v_2,v_3\}\), \(M_3(v_3)=\{v_2,v_3\}\), and \(M_3(v_2)=\{v_2\}\).

For \(k=3,\dots ,n-1\), step \(k-1\) constructs a planar straight-line drawing \(\varGamma _{k+1}\) of \(G_{k+1}\) by modifying \(\varGamma _{k}\) as follows; see Fig. 5. Let \(w_1=u,w_2,\dots ,w_{r}=v\) be the clockwise order of the vertices along the outer face of \(G_k\). Assume that step \(k-2\) has defined, for \(i=1,\dots ,r\), a subset \(M_k(w_i)\) of the vertices of \(G_k\), where \(M_k(w_1)\supset \dots \supset M_k(w_{r})\). Let \(w_p,w_{p+1},\dots ,w_q\) be the neighbors of \(v_{k+1}\) in \(G_k\), where \(p <q\). Then \(\varGamma _{k+1}\) is obtained from \(\varGamma _k\) by increasing the x-coordinate of each vertex in \(M_k(w_{p+1})\) by one unit, the x-coordinate of each vertex in \(M_k(w_q)\) by one additional unit, and placing \(v_{k+1}\) at the intersection of the line through \(w_p\) with slope \(+1\) and the line through \(w_q\) with slope \(-1\). Then step \(k-1\) proceeds to define the sets:

  1. (i)

    \(M_{k+1}(w_i)=M_k(w_i)\cup \{v_{k+1}\}\), for \(i=1,\dots ,p\);

  2. (ii)

    \(M_{k+1}(v_{k+1})=M_k(w_{p+1})\cup \{v_{k+1}\}\); and

  3. (iii)

    \(M_{k+1}(w_i)=M_{k}(w_i)\), for \(i=q,\dots ,r\).

We call the drawing \(\varGamma _n\) of G constructed by the FPP-algorithm; we often say that \(\varGamma _n\) to \(\pi \). The following is the main tool for our enumeration algorithm.

Theorem 5

Let G be an n-vertex maximal plane graph and (u, v, z) be the cycle delimiting the outer face of G, with u, v, and z in this counter-clockwise order along the cycle. There is a bijective function f from the canonical orientations of G with first vertex u to the canonical drawings of G with base edge (u, v). Also, given a canonical orientation with first vertex u, the corresponding canonical drawing with base edge (u, v) can be constructed in \(\mathcal {O}(n)\) time.

Proof (sketch):

The function f is as follows. Consider any canonical orientation \(\mathcal D\) of G with first vertex u and let \(\pi \) be any canonical ordering with first vertex u that \(\mathcal D\) (that is, the canonical orientation of G with respect \(\pi \) is \(\mathcal D\)). Then \(f(\mathcal D)\) is the canonical drawing with base edge (u, v) that corresponds to \(\pi \). Since \(\pi \) can be computed as any topological sorting of \(\mathcal D\) in \(\mathcal {O}(n)\) time [40] and the FPP-algorithm can be implemented in \(\mathcal {O}(n)\) time [17], the second part of the statement follows. Clearly, f is injective. Indeed, any distinct canonical orientations \(\mathcal D_1\) and \(\mathcal D_2\) of G differ on the orientation of some edge (a, b). Thus, for any two canonical orderings \(\pi _1\) and \(\pi _2\) that extend \(\mathcal D_1\) and \(\mathcal D_2\), respectively, we have that b follows a in \(\pi _1\) and precedes a in \(\pi _2\) (or vice versa). Hence, the y-coordinate of b is larger than the one of a in \(f(\mathcal D_1)\) and smaller than the one of a in \(f(\mathcal D_2)\) (or vice versa), thus \(f(\mathcal D_1)\) and \(f(\mathcal D_2)\) are not the same drawing. The core of the proof that f is surjective is in the proof of the following statement.

Claim 1

Any two canonical orderings \(\pi \) and \(\tau \) that extend \(\mathcal D\) are such that the canonical drawings of G corresponding to \(\pi \) and \(\tau \) are the same drawing.

The proof of Claim 1 is by induction on |V(G)| and it relies on a natural extension of the concepts of canonical ordering, orientation, and drawing to biconnected internally-triangulated plane graphs; hence, in the following, the outer face of G might have more than three incident vertices. The proof of Claim 1 exploits the following claim, which is also proved by induction on the size of G.

Claim 2

Let \(z_1,\dots ,z_{r}\) be the clockwise order of the vertices along the outer face of G, let \(M^{\pi }(z_1)\), \(\dots \), \(M^{\pi }(z_{r})\) (let \(M^{\tau }(z_1)\), \(\dots \), \(M^{\tau }(z_{r})\)) be the sets associated to \(z_1,\dots ,z_{r}\), respectively, by the FPP-algorithm, when applied with canonical ordering \(\pi \) (resp. \(\tau \)). For \(i=1,\dots ,r\), the sets \(M^{\pi }(z_i)\) and \(M^{\tau }(z_i)\) coincide.

The inductive proof of Claim 1 distinguishes two cases.

In Case 1, \(\pi \) and \(\tau \) have the same last vertex. This can be removed from both, resulting in canonical orderings \(\lambda \) and \(\xi \), respectively, of a smaller graph \(G'\). By induction, the canonical drawings of \(G'\) corresponding to \(\lambda \) and \(\xi \) coincide. This and the fact that the sets associated to the vertices along the boundary of \(G'\) by the FPP-algorithm when applied with canonical orderings \(\lambda \) and \(\xi \) coincide imply that the canonical drawings of G corresponding to \(\pi \) and \(\tau \) also coincide.

In Case 2, \(\pi \) and \(\tau \) do not have the same last vertex. Then we define a sequence of canonical orderings of G such that: (i) the first canonical ordering in the sequence is \(\tau \); (ii) any two canonical orderings consecutive in the sequence coincide, except for two vertices, whose positions are adjacent and swapped in the two canonical orderings; and (iii) the last canonical ordering in the sequence has the same last vertex as \(\pi \). Note that the last canonical ordering in the sequence and \(\pi \) are such that the corresponding canonical drawings of G are the same drawing, by Case 1. The proof that the canonical drawings of G corresponding to two consecutive canonical orderings in the sequence are the same drawing relies on the similarity of such canonical orderings. By transitivity, we get that the canonical drawings of G corresponding to \(\pi \) and \(\tau \) are the same drawing.   \(\square \)

Theorem 3 and Theorem 5 imply the following.

Theorem 6

There is an algorithm with \(\mathcal {O}(n)\) setup time and space usage listing all canonical drawings of an n-vertex maximal plane/planar graph with \(\mathcal {O}(n)\) delay.

4 Enumeration of Schnyder Woods and Drawings

We now show how to efficiently enumerate the Schnyder woods and drawings of an n-vertex maximal plane graph G. The Schnyder woods and the canonical orientations of G are in bijection [22]. Further, given a canonical orientation of G, the corresponding Schnyder wood of G can be constructed in \(\mathcal {O}(n)\) time [14, 16, 26, 27, 29, 43, 52]. This, together with Theorem 3, implies the following.

Theorem 7

There is an algorithm with \(\mathcal {O}(n)\) setup time and space usage listing all Schnyder woods of an n-vertex maximal plane/planar graph with \(\mathcal {O}(n)\) delay.

We now deal with the enumeration of the planar straight-line drawings produced by the algorithm by Schnyder [52], known as . The S-algorithm takes as input (see Fig. 6(a)) an n-vertex maximal plane graph G, whose outer face is delimited by a 3-cycle \((u_1,u_2,u_3)\), where \(u_1\), \(u_2\), and \(u_3\) appear in this counter-clockwise order along the cycle, and a Schnyder wood \(\mathcal W = (\mathcal T_1,\mathcal T_2, \mathcal T_3)\) of G, where \(\mathcal T_i\) contains \(u_i\), for \(i=1,2,3\).

Fig. 6.
figure 6

(a) A Schnyder wood \(\mathcal W\) of a maximal plane graph G. (b) Paths \(\mathcal P_1(4)\), \(\mathcal P_2(4)\), and \(\mathcal P_3(4)\), and cycles \(\mathcal C_x(4)\) and \(\mathcal C_y(4)\). (c) The Schnyder drawing \(s(\mathcal W)\).

Full size image

The S-algorithm assigns coordinates (0, 0), \((2n-5,0)\), and \((0,2n-5)\) to \(u_1\), \(u_2\), and \(u_3\), respectively. For a cycle \(\mathcal C\), let \(\#_f(\mathcal C)\) be the number of internal faces of G inside \(\mathcal C\). For \(i=1,2,3\), properties (S-1) and (S-2) of \(\mathcal W\) imply that \(\mathcal T_i\) contains a directed path \(\mathcal P_i(w)\) from any internal vertex w to \(u_i\); see Fig. 6(b). Also, \(\mathcal P_1(w)\), \(\mathcal P_2(w)\), and \(\mathcal P_3(w)\) only share w [52]. Let \(\mathcal C_x(w)\) and \(\mathcal C_y(w)\) be the cycles \(\mathcal P_1(w)\cup \mathcal P_3(w) \cup (u_1,u_3)\) and \(\mathcal P_1(w)\cup \mathcal P_2(w)\cup (u_1,u_2)\), respectively. Then the algorithm assigns coordinates \((\#_f(\mathcal C_x(w)),\#_f(\mathcal C_y(w)))\) to w; see Fig. 6(c).

The following is the main tool for our enumeration algorithm.

Theorem 8

Let G be an n-vertex maximal plane graph. There is a bijective function s from the Schnyder woods of G to the Schnyder drawings of G. Also, given a Schnyder wood of G, the corresponding Schnyder drawing of G can be constructed in \(\mathcal {O}(n)\) time.

Proof (sketch):

The function s is the S-algorithm, which can be implemented in \(\mathcal {O}(n)\) time [52], from which the second part of the statement follows. The core of the proof that s is bijective consists of proving that a Schnyder drawing \(\varGamma \) uniquely determines the Schnyder wood \(\mathcal W = (\mathcal T_1,\mathcal T_2, \mathcal T_3)\) such that \(s(\mathcal W)=\varGamma \). This follows from the fact that in \(\varGamma \), for each vertex v of G, the edges of \(\mathcal T_1\), \(\mathcal T_2\), and \(\mathcal T_3\) incoming into v have slopes in the intervals \((0^\circ ,90^\circ )\), \((135^\circ ,180^\circ )\), and \((270^\circ ,315^\circ )\), respectively, while the edges of \(\mathcal T_1\), \(\mathcal T_2\), and \(\mathcal T_3\) outgoing from v have slopes in the intervals \((180^\circ ,270^\circ )\), \((315^\circ ,360^\circ )\), and \((90^\circ ,135^\circ )\), respectively; see [27]. Thus, whether each edge (u, v) of G belongs to \(\mathcal T_1\), \(\mathcal T_2\), or \(\mathcal T_3\) and whether it is directed from u to v or vice versa is uniquely determined by its slope in \(\varGamma \).    \(\square \)

Theorem 7 and Theorem 8 imply the following.

Theorem 9

There is an algorithm with \(\mathcal {O}(n)\) setup time and space usage listing all Schnyder drawings of an n-vertex maximal plane graph with \(\mathcal {O}(n)\) delay.