A Polynomial Delay Algorithm Generating All Potential Maximal Cliques in Triconnected Planar Graphs

In this paper, all graphs of main interest are simple, that is, without self loops or parallel edges. Let $G$ be a graph. We denote by $V(G)$ the vertex set of $G$ and by $E(G)$ the edge set of $G$. When the vertex set of $G$ is $V$, we say that the graph $G$ is on $V$. The complete graph on $V$, denoted by $K(V)$, is a graph on $V$ where every vertex is adjacent to all other vertices. A complete graph $K(V)$ is a $K_n$ if $|V|=n$.

A graph $H$ is a subgraph of a graph $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. The subgraph of $G$ induced by $U\subseteq V(G)$ is denoted by $G[U]$: its vertex set is $U$ and its edge set is $\{\{u,v\}\in E(G)\mid u,v\in U\}$. A vertex set $C\subseteq V(G)$ is a clique of $G$ if $G[C]$ is a complete graph. For each $v\in V(G)$, $N_G(v)$ denotes the set of neighbors of $v$ in $G$: $N_G(v)=\{u\in V(G)\mid \{u,v\}\in E(G)\}$. The degree of $v$ in $G$ is $|N_G(v)|$. For $U\subseteq V(G)$, the open neighborhood of $U$ in $G$, denoted by $N_G(U)$, is the set of vertices adjacent to some vertex in $U$ but not belonging to $U$ itself: $N_G(U)=({\bigcup }_{v\in U}{N}_G(v))\setminus U$. For an edge set $E\subseteq E(G)$ we denote by $V(E)$ the set of vertices of $G$ incident to some edge in $E$.

We say that a vertex set $C\subseteq V(G)$ is connected in $G$ if, for every $u,v\in C$, there is a walk of $G[C]$ starting with $u$ and ending with $v$, where a walk of $G$ is a sequence of vertices in which every vertex except for the last is adjacent to the next vertex in the sequence. It is a connected component or simply a component of $G$ if it is connected and is inclusion-wise maximal subject to connectivity. For each vertex set $S$ of $G$, we denote by ${𝒞}_G(S)$ the set of components of $G[V(G)\setminus S]$. When $G$ is clear from the context we may drop the subscript and write $𝒞(S)$ for ${𝒞}_G(S)$. A vertex set $S\subseteq V(G)$ is a separator of $G$ if $|{𝒞}_G(S)|\ge 2$. We usually assume that $G$ is connected and therefore $\mathrm{\varnothing }$ is not a separator of $G$. A component $C\in {𝒞}_G(S)$ is a full component associated with $S$ if $N_G(C)=S$. A graph $G$ is biconnected (triconnected) if every separator of $G$ is of cardinality two (three) or greater. A graph is a cycle if it is connected and every vertex is adjacent to exactly two vertices. A graph is a tree if it is connected and does not contain a cycle as a subgraph. A tree is a path if it has exactly two vertices of degree one or its vertex set is a singleton. Those two vertices of degree one are called the ends of the path. If $p$ is a path with ends $a$ and $b$, we say that $p$ is between $a$ and $b$. When we speak of cycles or paths of $G$, we mean subgraphs of $G$ that are cycles or paths. Let $p$ be a cycle or path of $G$. A chord of $p$ in $G$ is an edge $\{u,v\}$ of $G$ with $u,v\in V(p)$ that is not an edge of $p$. A cycle or path of $G$ is chordless if it does not have any chord in $G$.

A tree-decomposition of $G$ is a pair $(T,𝒳)$ where $T$ is a tree and $𝒳$ is a family ${\{X_i\}}_{i\in V(T)}$ of vertex sets of $G$, indexed by the nodes of $T$, such that the following three conditions are satisfied. We call each $X_i$ the bag at node $i$.

1. 1.

   ${\bigcup }_{i\in V(T)}{X}_i=V(G)$.

2. 2.

   For each edge $\{u,v\}\in E(G)$, there is some $i\in V(T)$ such that $u,v\in X_i$.

3. 3.

   For each $v\in V(G)$, the set of nodes $I_v=\{i\in V(T)\mid v\in X_i\}\subseteq V(T)$ is connected in $T$.

The width of this tree-decomposition is ${\max }_{i\in V(T)}|X_i|-1$. The treewidth of $G$, denoted by $tw(G)$ is the smallest $k$ such that there is a tree-decomposition of $G$ of width $k$.

Let $G$ be a graph and $S$ a separator of $G$. For distinct vertices $a,b\in V(G)$, $S$ is an $a$-$b$ separator if there is no path between $a$ and $b$ in $G[V(G)\setminus S]$; it is a minimal $a$-$b$ separator if it is an $a$-$b$ separator and no proper subset of $S$ is an $a$-$b$ separator. A separator is a minimal separator if it is a minimal $a$-$b$ separator for some $a,b\in V(G)$. A necessary and sufficient condition for a separator $S$ of $G$ to be minimal is that ${𝒞}_G(S)$ has at least two members that are full components associated with $S$. We say that a connected vertex set $C$ of $G$ is minimally separated if $N_G(C)$ is a minimal separator.

Graph $H$ is chordal if every cycle of $H$ with four or more vertices has a chord in $H$. $H$ is a triangulation of graph $G$ if it is chordal, $V(G)=V(H)$, and $E(G)\subseteq E(H)$. A triangulation $H$ of $G$ is minimal if there is no triangulation $H^{\prime }$ of $G$ such that $E(H^{\prime })$ is a proper subset of $E(H)$.

A vertex set $X$ of $G$ is a potential maximal clique (PMC for short) of $G$ if there is some minimal triangulation $H$ of $G$ such that $X$ is a maximal clique of $H$. We denote by $\mathrm{\Pi }(G)$ the set of all PMCs of $G$. The following lemmas due to Bouchitté and Todinca [8] are essential in our reasoning about PMCs.

They also show that PMCs are extremely useful for computing the treewidth.

We need the following property of PMCs.

A sphere-embedded graph is a graph where a vertex is a point on the sphere $\mathrm{\Sigma }$ and each edge is a simple curve on $\mathrm{\Sigma }$ between two distinct vertices that does not contain any vertex except for its ends. In the combinatorial view of a sphere-embedded graph $G$, an edge represents the adjacency between two vertices at its ends. A sphere-embedded graph $G$ is a plane graph if no two edges of $G$ intersect each other as curves except at their ends. A graph $G$ is planar if there is a plane graph that is isomorphic to $G$ in the combinatorial view. We call this plane graph a planar embedding of $G$.

Let $G$ be a biconnected plane graph. Then the removal of all the edges of $G$ from the sphere $\mathrm{\Sigma }$ results in a collection of regions homeomorphic to open discs. We call these regions the faces of $G$. Each face of $G$ is bounded by a simple closed curve that consists of edges of $G$. A vertex or an edge of $G$ is incident to a face $f$ of $G$, if it is contained in the closed curve that bounds $f$. We denote by $F(G)$ the set of faces of $G$. For each $f\in F(G)$, we denote by $V(f)$ the set of vertices of $G$ incident to $f$.

A combinatorial representation of a plane graph $G$ is an indexed set ${\{{\pi }_v\}}_{v\in V(G)}$, where ${\pi }_v$ is a permutation on $N_G(v)$ such that ${\pi }_v(u)$ for $u\in N_G(v)$ is the neighbor of $v$ that comes immediately after $u$ in the clockwise order around $v$. Suppose we have two planar embeddings $G_1$ and $G_2$ of a graph $G$ and assume that $V(G_1)=V(G_2)=V(G)$ and moreover the isomorphisms between $G_1$ and $G$ as well as between $G_2$ and $G$ are identities. Let, for $i\in \{1,2\}$, the combinatorial representation of $G_i$ be ${\{{\pi }_{i,v}\}}_{v\in V(G)}$. We say that these two planar embeddings are combinatorially equivalent if either ${\pi }_{1,v}={\pi }_{2,v}$ for every $v\in V(G)$ or ${\pi }_{1,v}={({\pi }_{2,v})}^{-1}$ for every $v\in V(G)$. In this paper, we mainly deal with triconnected planar graphs. It is known that, for a triconnected planar graph $G$, the planar embedding of $G$ is unique up to combinatorial equivalence [22]. For this reason, we will be dealing with triconnected plane graphs rather than triconnected planar graphs.

In conventional approaches for branch-decompositions and tree-decompositions of plane graphs [19, 6], the standard tools are radial graphs and nooses. We observe that, for triconnected plane graphs, latching graphs as defined below may replace those tools and greatly simplify definitions and reasoning.

Figure 1 shows a triconnected plane graph with its latching graph and a plane graph for which the latching graph is not simple.

Let $G$ be a triconnected plane graph and let $u$ and $v$ be two vertices of $G$. It is straightforward to see, and is observed in [6], that there are exactly two faces of $G$ to which both $u$ and $v$ are incident if $\{u,v\}$ is an edge of $G$ and there is at most one such face otherwise. In the first case, there is no face in which $\{u,v\}$ is a chord and, in the second case, there is at most one face in which $\{u,v\}$ is a chord. Thus, there is at most one edge between $u$ and $v$ in $L_G$ and therefore $L_G$ is simple. $◀$

Although the latching graph $L_G$ of a triconnected plane graph $G$ is not a plane graph in general, we are interested in its subgraphs that are plane graphs. For $X\subseteq V(G)$, the subgraph of $L_G$ induced by $X$, denoted by $L_G[X]$, is a sphere-embedded graph with vertex set $X$ that inherits all edges of $L_G$, as curves, with two ends in $X$.

Since $V(f)\cap X$ forms a clique of $L_G[X]$ for each face $f$ of $G$, $L_G[X]$ is not a plane graph if there is some face $f$ such that $|V(f)\cap X|\ge 4$. Conversely, if $L_G[X]$ has an edge-crossing, it must be in some face $f$ of $G$ and we have $|V(f)\cap X|\ge 4$. $◀$

Let $X\subseteq V(G)$ such that $L_G[X]$ is a biconnected plane graph. We call each face of $L_G[X]$ a region of $L_G[X]$, in order to avoid confusions with the faces of $G$. We say that a region $r$ of $L_G[X]$ is empty if $r$ does not contain any vertex of $G$.

We use this framework to formulate the fundamental observation on minimal separators of triconnected plane graphs, which is conventionally stated in terms of nooses [6].

The following fact is essential in our treatment of PMCs of triconnected plane graphs.

Suppose $L_G[X]=H$ where $H$ is an $(S,P)$-steering. This equality means an equality as plane graphs, since we are viewing a steering as a biconnected plane graph, as we mentioned in the remark following Proposition 14.

Due to Proposition 8, each component in ${𝒞}_G(X)$ is contained in a region of $H$ and each region of $H$ contains at most one component in ${𝒞}_G(X)$.

We show that $X$ satisfies the two conditions for PMCs in Lemma 2: (1) There is no full component associated with $X$; (2) For every pair of vertices $x$ and $y$ in $X$, either $x$ is adjacent to $y$ in $G$ or there is some $C\in {𝒞}_G(X)$ such that $x,y\in N_G(C)$.

To show that Condition (1) holds, let $C$ be an arbitrary component in ${𝒞}_G(X)$ and ${\gamma }_C$ be the cycle bounding the region of $H$ containing $C$. If ${\gamma }_C$ is $H[S]$, then $C$ is not a full component associated with $X$ as $S$ is a proper subset of $X$. Otherwise, there is a vertex in $S$ that does not belong to ${\gamma }_C$, since $N_H(P)$ is not a slot of the cycle $H[S]$, and therefore $C$ is not a full component associated with $X$.

To show that Condition (2) holds, we first show that, for arbitrary two members $x$ and $y$ of $X$, there is some region of $H$ whose boundary contains both $x$ and $y$. If $x,y\in S$, then this certainly holds since $H$ has a region bounded by the cycle $H[S]$. So suppose that at least one of $x$ and $y$, say $x$, belongs to $P$. We argue in a few cases.

First suppose that $|P|=1$ and hence $P=\{x\}$ and $y\in S$. Then, there is certainly a region of $H$ bounded by a cycle consisting of $x$ and a subpath of the cycle $H[S]$ that contains $y$. See the first three examples in Figure 2.

Next suppose that $|P|\ge 2$. Since there is no internal vertex of the path $H[P]$ adjacent in $H$ to any vertex in $S$, there are two regions of $H$ bounded by cycles containing the path $H[P]$. Let ${\gamma }_1$ and ${\gamma }_2$ be those cycles. Then, ${\gamma }_i$, for each $i\in \{1,2\}$, consists of $H[P]$ and a subpath $p_i$ of $H[S]$. Since $N_H(t)\cap S$ for each end $t$ of the path $H[P]$ is a slot, we have $V(p_1)\cap V(p_2)=S$. Therefore, either ${\gamma }_1$ or ${\gamma }_2$ contains both $x$ and $y$. See the last three examples in Figure 2.

We are ready to show that Condition (2) holds. Let $x$ and $y$ be arbitrary two vertices in $X$. As we have shown above, there is a cycle $\gamma$ bounding a region of $H$ such that $x,y\in V(\gamma )$. If this region contains some $C\in {𝒞}_G(X)$, then we are done since $N_G(C)=V(\gamma )$. Otherwise, $\gamma$ bounds an empty region and must be a triangle since otherwise $L_G[X]$ would not be a plane graph. Therefore, $\{x,y\}$ is an edge of $L_G[X]$. If this is an edge of $G$ then we are done, so suppose not. Let ${\gamma }^{\prime }$ be another cycle bounding a region of $L_G[X]$ that contains the edge $\{x,y\}$. This region bounded by ${\gamma }^{\prime }$ cannot be empty since, if it were, then we would have a face of $G$ incident to four or more vertices of $X$, and $L_G[X]$ would not be a plane graph. We are done, since $x,y\in N_G(C^{\prime })$ where $C^{\prime }$ is the member of ${𝒞}_G(X)$ contained in the region bounded by ${\gamma }^{\prime }$. $◀$

The converse of this lemma is shown in several steps. We start with a technical proposition.

If $L_G[X^{\prime }]$ is a steering, $X^{\prime }$ is a PMC of $G$ due to Lemma 15. Since no proper subset of a PMC is a PMC (Lemma 4), we have $X=X^{\prime }$. $◀$

The next lemma deals with a special case where every minimal separator contained in a PMC $X$ consists of three vertices.

Recall that, due to Proposition 12, $L_G[X]$ is a biconnected plane graph. Recall also that every $C\in {𝒞}_G(X)$ is contained in a region of $L_G[X]$ bounded by a cycle whose vertex set is $N_G(C)$. Let $\gamma$ be a cycle that bounds a region $r$ of $L_G[X]$ and let $S=V(\gamma )$. If $r$ is empty then $|S|=3$ since otherwise $L_G[X]$ would not be a plane graph (Proposition 7). Otherwise $r$ contains some $C\in {𝒞}_G(X)$ and we also have $|S|=3$ due to the assumption. Let $x\in X\setminus S$ and $s\in S$ be arbitrary. We show that $x$ is adjacent to $s$ in $L_G[X]$. If $x$ is adjacent to $s$ in $G$ then we are done. Otherwise, due to the second condition for PMCs in Lemma 2, there is some $C\in {𝒞}_G(X)$ such that $x,s\in N_G(C)$. Since the region of $L_G[X]$ containing $C$ is bounded by a triangle on $N_G(C)$, $x$ is adjacent to $s$ in $L_G[X]$. Therefore, $x$ is adjacent in $L_G[X]$ to every $s\in S$ and hence $L_G[S\cup \{x\}]$ is a $K_4$. As $L_G[S\cup \{x\}]$ is an $(S,\{x\})$-steering, we have $X=S\cup \{x\}$ due to Proposition 16 and hence $L_G[X]$ is a $K_4$. $◀$

To deal with the more general case, we use the following notion of arches.

If $L_G[S\cup P]$ is an $(S,P)$-steering, then $P$ is certainly an arch of $S$. The converse does not hold: if $P$ is an arch of $S$ then $L_G[S\cup P]$ is not necessarily an $(S,P)$-steering, as the definition of steerings requires more conditions to be satisfied by $L_G[S\cup P]$. We show, however, in the next lemma that if $P$ is an inclusion-wise minimal arch then $L_G[S\cup P]$ is a steering. A caveat: $L_G[S\cup P]$ is not necessarily an $(S,P)$-steering in this case; it may be an $(S^{\prime },\{s\})$-steering where $S^{\prime }=(S\cup P)\setminus \{s\}$ for some $s\in S$. In Lemma 20, we show that if $X$ is a PMC then every minimal separator $S\subset X$ with $|S|\ge 4$ has an arch $P$ that is a subset of $X\setminus S$. It follows from these two lemmas that, for every minimal separator $S$ with $|S|\ge 4$ that is a subset of a PMC $X$, there is some $P\subset X\setminus S$ such that $L_G[S\cup P]$ is a steering. Due to Lemma 15, $S\cup P$ is a PMC and, since no proper subset of a PMC is a PMC (Lemma 4), we conclude that $X=S\cup P$ and $L_G[X]$ is a PMC, which is an essential part of Theorem 21.

If there is some $v\in P$ such that $N_{L_G}(v)\cap S$ is neither empty nor a slot of the cycle $L_G[S]$, then $\{v\}$ is an arch of $S$ and, since $P$ is minimal, $P=\{v\}$. We are done, since $H$ is an $(S,\{v\})$-steering.

Suppose $N_{L_G}(v)\cap S$ is either empty or a slot of $L_G[S]$ for every $v\in P$. Since $N_{L_G}(P)\cap S$ is not a slot of $L_G[S]$, there are two vertices $v_1,v_2\in P$ and two vertices $s_1,s_2\in S$ such that $v_i$ is adjacent to $s_i$ for $i\in \{1,2\}$ and $\{s_1,s_2\}$ is not an edge of $S$. Let $p$ be a shortest path in $L_G[P]$ between $v_1$ and $v_2$. Then, $V(p)$ is an arch of $S$ and, since $P$ is minimal, $P$ must be equal to $V(p)$. If no internal vertex of $p$ is adjacent in $L_G$ to any vertex in $S$, then $L_G[S\cup P]$ is an $(S,P)$-steering and we are done. So suppose an internal vertex $v$ of $p$ is adjacent to some vertex in $S$. Let $p_i$ be the subpath of $p$ between $v_i$ and $v$, for $i\in \{1,2\}$. Since $P$ is a minimal arch of $S$, neither $V(p_1)$ nor $V(p_2)$ is an arch of $S$. Therefore, $N_{L_G}(\{v_i,v\})\cap S$ is a slot for $i\in \{1,2\}$. This is possible only if there is a vertex $s\in S$ such that $s$ is adjacent to both $s_1$ and $s_2$ on $L_G[S]$, $N_{L_G}(v_i)$ is either $\{s_i\}$ or $\{s_i,s\}$ for $i\in \{1,2\}$, and $N_{L_G}(v)\cap S=\{s\}$. Moreover, since $P=V(p)$ is a minimal arch of $S$, no vertices in $P$ other than $v$, $v_1$, or $v_2$ are adjacent to any vertex in $S$. Let $p_3$ be the subpath of $L_G[S]$ between $s_1$ and $s_2$ avoiding $s$ and let $\gamma$ be the cycle consisting of $p_3$ and $p$. Let $S^{\prime }=V(\gamma )=(S\cup P)\setminus \{s\}$. We claim that $\gamma$ is chordless in $L_G$, that is, $L_G[S^{\prime }]=\gamma$. This is because $p_3$ is chordless since $L_G[S]$ is a cycle by assumption, $p$ is chordless since it is the shortest path in $P$ between $v_1$ and $v_2$, and the only edges between $V(p)$ and $V(p_3)$ are the edges $\{v_1,s_1\}$ and $\{v_2,s_2\}$. Since $N_{L_G}(s)\cap S^{\prime }=\{s_1,v,s_2\}$, $L_G[S\cup P]$ is an $(S^{\prime },\{s\})$-steering as desired. $◀$

Due to Lemma 1, $X\setminus S$ is non-empty and is a subset of one of the two full components associated with $S$. Let $r_0$ be the region of $L_G[S]$ that contains $X\setminus S$.

Suppose that there is no arch $P$ of $S$ such that $P\subseteq X\setminus S$. Then, for every pair of vertices $s$ and $s^{\prime }$ in $S$ that are not adjacent to each other on the cycle $L_G[S]$, we can draw a curve between $s$ and $s^{\prime }$ in $r_0$ without crossing the drawing of $L_G[X]$. Therefore, there is a region $r$ of $L_G[X]$ contained in $r_0$ that is incident to all vertices in $S$. Let $\gamma$ be the cycle of $L_G[X]$ bounding $r$. Since $|V(\gamma )|\ge |S|\ge 4$, $r$ is non-empty (Proposition 8) and hence contains a component $C\in {𝒞}_G(X)$. Therefore, $V(\gamma )$ must be a minimal separator of $G$, due to Lemma 1. But this is impossible, since some edge of $L_G[S]$ is a chord of $\gamma$, contradicting Proposition 9. $◀$

The following is our main theorem in this section.

Lemma 15 shows that if $L_G[X]$ is a steering then $X$ is a PMC. We prove the other direction. Let $X$ be a PMC of $G$.

If $|N_G(C)|=3$ for every $C\in {𝒞}_G(X)$, $L_G[X]$ is a $K_4$ due to Lemma 17 and hence is an $(X\setminus \{x\},\{x\})$-steering for every $x\in X$.

Suppose there is some $C\in {𝒞}_G(X)$ with $|S|\ge 4$ where $S=N_G(C)$. Due to Lemma 20, there is an arch of $S$ that is a subset of $X\setminus S$. Let $P$ be an inclusion-wise minimal arch of $S$ that is a subset of $X\setminus S$. Due to Lemma 19, $L_G[S\cup P]$ is a steering and hence $S\cup P$ is a PMC of $G$, due to Lemma 15. Due to Proposition 16, $X=S\cup P$ and hence $L_G[X]$ is a steering. $◀$

Given $G$, we generate all chordless cycles of $L_G$ with polynomial delay, using the algorithm of Uno and Satoh. These chordless cycles are in one-to-one correspondence with minimal separators of $G$ due to Proposition 9. For the second part, we generate all chordless cycles of $G[V(G)\setminus \{v\}]$. Since a chordless cycle of $G[V(G)\setminus \{v\}]$ is a chordless cycle of $G$, we have the result. $◀$

To design an algorithm to generate all PMCs based on our characterization of PMCs stated in Theorem 21, we need some preparations.

Ports are potential ends of a path $p$ such that $L_G[X]$ for $X=S\cup V(p)$ is a steering. A pair of ports must be valid in order for the pair to be the ends of such path $p$. We generate such paths using the algorithm for generating chordless paths. The following lemma is the basis of this approach.

For part 1, suppose $L_G[X]$ is an $(S,P)$-steering where $P\subseteq C^{\prime }$. Let $H=L_G[X]$. Due to Definition 13, $H[P]=L_G[P]$ is a path. Let $u_1$ and $u_2$ be the two ends of this path. Then, $u_1$ and $u_2$ are ports of $S$ and, moreover, the pair of these ports is valid. Since no internal vertex of the path $L_G[P]$ is adjacent in $L_G$ to any vertex in $S$, $L_G[P]$ is a path in $A(C,u_1,u_2)$. It is a chordless path, since if it had a chord in $A(C,u_1,u_2)$, then the graph $L_G[P]$ would contain that chord and $L_G[P]$ would not be a path.

For the other direction, suppose that there is a valid pair of ports $u_1$ and $u_2$ of $S$ such that $L_G[P]$ is a chordless path of $A(C,u_1,u_2)$ between $u_1$ and $u_2$. Then, $N_{L_G}(P\setminus \{u_1,u_2\})\cap S$ is empty and hence $L_G[S\cup P]$ is an $(S,P)$-steering.

For part 2, suppose $L_G[X]$ is an $(S^{\prime },\{s\})$-steering where $s\in S$ and $S^{\prime }=X\setminus \{s\}$. Due to the proof of Lemma 19, $L_G[P]$ is a path of $L_G$ between some valid pair of ports $u_1$ and $u_2$ of $(S,C)$ and, moreover, $s$ is a hinge of this pair of ports. Since the only vertex in $S$ that can be adjacent to any internal vertex of $L_G[P]$ is $s$, $L_G[P]$ is a path in $B(C,u_1,u_2,s)$ between $u_1$ and $u_2$. It is a chordless path, since if it had a chord in $B(C,u_1,u_2,s)$, then the graph $L_G[P]$ would contain that chord and $L_G[P]$ would not be a path.

For the other direction, suppose that there is a valid pair of ports $u_1$ and $u_2$ of $S$ with a hinge $s$ such that $L_G[P]$ is a chordless path of $B(C,u_1,u_2,s)$ between $u_1$ and $u_2$. Then, $L_G[S^{\prime }]$, where $S^{\prime }=X\setminus \{s\}$, is a cycle and $L_G(X)$ is an $(S^{\prime },\{s\})$-steering. $◀$

In implementing the generation of PMCs based on this lemma, we need to deal with the problem of suppressing duplicate outputs of a single element without introducing super-polynomial delay. We use the technique due to Bergougnoux, Kanté and Wasa [1] to address this problem. They used this technique for a particular problem of generating what they call minimal disjunctive separators. We formulate their technique in the following theorem that can be used for wide range of generation problems.

Let $G$ be a graph on $n$ vertices. We consider the general task of generating some structures defined on $G$. Let $𝒮(G)$ denote the set of those structures to be generated. Suppose $N$ subsets ${𝒮}_1(G)$, …, ${𝒮}_N(G)$ of $𝒮(G)$ are defined. Let $I=\{i\mid 1\le i\le N\}$. Suppose that the following conditions are satisfied.

1. 1.

   $𝒮(G)={\bigcup }_{i\in I}{𝒮}_i(G)$.

2. 2.

   $N=n^{O(1)}$.

3. 3.

   For each $s\in 𝒮(G)$ and $i\in I$, it can be decided whether $s\in {𝒮}_i(G)$ in time $n^{O(1)}$.

4. 4.

   For each $i\in I$, there is an algorithm ${\text{Gen}}_i$ that generates ${𝒮}_i(G)$ with polynomial delay.

We prove this theorem by showing that Algorithm 1 generates $𝒮(G)$ with polynomial delay. The idea of this algorithm is as follows. For each $s\in 𝒮(G)$, let us say that $i\in I$ owns $s$ if $i$ is the largest $j$ such that $s\in {𝒮}_j(G)$. We let ${\text{Gen}}_i$, where $i$ owns $s$, be responsible for the output of $s$ and suppress the output of $s$ from ${\text{Gen}}_j$ for other $j$. The executions of ${\text{Gen}}_i$ for $i\in I$ are scheduled in such a way that at most a polynomial number of outputs are suppressed before an unsuppressed output occurs.

We now turn to the application of this technique to our goal.

For a minimally separated component $C$ of a triconnected plane graph $G$ with $|S|\ge 4$ where $S=N_G(C)$, let $\mathrm{\Pi }(G,C)$ denote the set of PMCs $X$ such that $C\in {𝒞}_G(X)$ and $L_G[X]$ is a steering.

Let $S=N_G(C)$ and let $C^{\prime }$ be the other full component of $S$. Let $H$ be an arbitrary minimal triangulation of $G$ in which $S$ is a clique. Let $X$ be an arbitrary maximal clique of $H[S\cup C^{\prime }]$ that contains $S$. Since $S$ is a separator of $H$, $X$ is a maximal clique of $H$. Since no maximal clique of a chordal graph is a minimal separator, $X$ is a proper superset of $S$ and belongs to $\mathrm{\Pi }(G,C)$. $◀$

Based on Lemma 26, we generate $\mathrm{\Pi }(G,C)$ as follows. We first generate $X\in \mathrm{\Pi }(G,C)$ such that $L_G[X]$ is an $(S,P)$-steering where $P=X\setminus S$. To do so, for every valid pair of ports $u_1$ and $u_2$ of $S$, we generate all chordless paths of $A(C,u_1,u_2)$ between $u_1$ and $u_2$, where $A(C,u_1,u_2)$ is as defined in Lemma 26, using the algorithm due to Sato and Uno given in Lemma 22. For each path $p$ generated, we output $S\cup V(p)$. Since the number of valid pairs of ports is $O(n^2)$, the generation of $X$ in this category is with polynomial delay even if some valid pairs do not yield any such $X$.

We then generate $X\in \mathrm{\Pi }(G,C)$ such that $L_G[X]$ is an $(S^{\prime },\{s\})$-steering where $s\in S$ and $S^{\prime }=X\setminus \{s\}$. To do so, for every valid pair of ports $u_1$ and $u_2$ of $S$ with hinges and for each hinge $s$ of this pair, we generate all chordless paths of $B(C,u_1,u_2,s)$ between $u_1$ and $u_2$. For each path $p$ generated, we output $S\cup V(p)$. The valid pair of $u_1$ and $u_2$ may have more than one ports when $|S|=4$, which could cause duplicate outputs of an identical $X$. We suppress such duplicate outputs using Theorem 27. Let $𝒯$ be the set of all triples $(u_1,u_2,s)$ where $(u_1,u_2)$ is a valid pair of ports of $(S,C)$ and $s$ is a hinge of this pair. Index the set $𝒯$ by $I=\{1,\mathrm{\dots },N\}$ where $N=|𝒯|$. For each $i\in I$, let ${𝒫}_i$ denote the set of chordless paths of $B(C,u_1,u_2,s)$ between $u_1$ and $u_2$, where $(u_1,u_2,s)$ is the triple in $𝒯$ indexed by $i$. Let $𝒫={\bigcup }_{i\in I}{𝒫}_i$. Our goal is to generate $𝒫$ without duplication. We verify the conditions for Theorem 27 to be applied.

1. 1.

   $𝒫={\bigcup }_{i\in I}{𝒫}_i$ by definition.

2. 2.

   $N=|I|=O(n^3)$.

3. 3.

   For each path $p$ in $𝒫$ and each $i\in I$, it can be decided whether $p\in {𝒫}_i$ in time $n^{O(1)}$.

4. 4.

   For each $i\in I$, we can generate ${𝒫}_i$ with polynomial delay as described above.

Therefore, Theorem 27 applies and we can generate $𝒫$ and hence all PMCs $X$ in this category, with polynomial delay. $◀$