# On the Two Paths Theorem and the Two Disjoint Paths Problem

Samuel Humeau, Damien Pous

<figure><img src="image_1.png" /></figure>

## To cite this version:

Samuel Humeau, Damien Pous. On the Two Paths Theorem and the Two Disjoint Paths Problem. 2025. hal-05077563v2

HAL Id: hal-05077563

https://hal.science/hal-05077563v2

Preprint submitted on 13 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ON THE TWO PATHS THEOREM AND THE TWO DISJOINT PATHS PROBLEM

SAMUEL HUMEAU* AND DAMIEN POUS*

**Abstract.** A tuple $(s_1, s_2, t_1, t_2)$ of vertices in an undirected graph is 2-linked when there are two vertex-disjoint paths, respectively from $s_1$ to $t_1$ and $s_2$ to $t_2$. A graph is 2-linked when all such tuples are 2-linked.

We give a new and simple proof of the "two paths theorem", a characterisation of edge-maximal graphs which are not 2-linked as *webs*: particular near triangulations filled with cliques. Our proof works by generalising the theorem, replacing the four vertices above by an arbitrary tuple; it does not require major theorems such as Kuratowski's or Menger's theorems. Instead, it follows an inductive characterisation of generalised webs via *parallel composition*, an operation consisting in taking a disjoint union and identifying some pairs of vertices.

We use the insights provided by this proof to design a simple $O(nm)$ recursive algorithm for the "two vertex-disjoint paths" problem. This algorithm returns either two disjoint paths, or an embedding of the input graph into a web.

**Key words.** Graphs, connectedness, linkage, disjoint paths problem, two paths theorem

**MSC codes.** 05C38, 05C75, 05C85

## 1. Introduction.

1.1. **Two paths theorem.** A graph is called *2-linked* if for all pairwise distinct vertices $s_1, t_1, s_2, t_2$, there are two disjoint paths, respectively from $s_1$ to $t_1$ and from $s_2$ to $t_2$. Such a pair of paths is called an (*s*₁, *s*₂, *t*₁, *t*₂)-*linkage*.

A *rib* is a planar graph such that in one of its plane embeddings, the outer face is a cycle of length four, all inner faces are triangles, and all triangles are inner faces. A *web* is a graph constructed from a rib *R* by adding one clique *K*<sub>*T*</sub> per triangle *T* of *R*, making vertices of *K*<sub>*T*</sub> adjacent to exactly the vertices of *T*. The outer face of a rib or of a web is called its *frame*.

**THEOREM 1.1** (Two paths theorem [10, 6]). *The edge-maximal graphs which are not 2-linked are the webs.*

This theorem is easily shown equivalent to the following one, where we call *edge extension* of a graph any graph obtained from it by adding a new edge.

**THEOREM 1.2** (Two paths theorem variant). *Let $s_1, s_2, t_1, t_2$ be four distinct vertices in a graph $G$. The following are equivalent:*

1. *G is a web with frame* $s_1s_2t_1t_2s_1$,

2. *every edge extension of G contains an (s₁, s₂, t₁, t₂)-linkage, but not G.*

To prove this theorem, Thomassen [10] reduces the problem along small separators and then relies on Kuratowski's theorem. Independently, Seymour [6] sketched a proof reducing the problem to the 2-connected case before doing a clever combinatorial analysis of the graph's separators. Both proofs moreover use Menger's theorem.

We give a new and direct proof of this theorem. We consider for that the slight generalisation of ribs and webs where the frame (the outer cycle in the near triangulation of the plane) does not need to have length four, but some number $k \ge 3$. Small webs are depicted in Figure 1. These are actually ribs; filling some of their triangles

<footnote>*Plume, LIP, CNRS, ENS de Lyon, France
samuel.humeau@ens-lyon.fr, https://perso.ens-lyon.fr/samuel.humeau
damien.pous@ens-lyon.fr, https://perso.ens-lyon.fr/damien.pous</footnote>
<figure><img src="image_3.png" /><figcaption>FIG. 1. Small ribs, with frames of size three, four, four, five, five, and six.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIG. 2. Decompositions of the non-trivial ribs from Figure 1.</figcaption></figure>

with arbitrary cliques would give examples of webs which are not ribs.

Accordingly, we also generalise the notion of linkage: a cycle $C = x_1x_2...x_kx_1$ in a graph is *crossed* when there are two vertex-disjoint paths from $x_i$ to $x_j$ and $x_r$ to $x_s$ with $i < r < j < s$, and *crossless* otherwise. A graph $G$ is *maximally C-crossless* when $C$ is crossless in $G$, but crossed in any edge extension of $G$.

Observe that none of the frames is crossed in the ribs from Figure 1, and that adding any edge to those graphs makes their frame crossed. These facts remain unchanged under filling triangles with cliques to obtain proper webs; this leads us to the following generalisation of the two paths theorem:

**THEOREM 1.3 (Generalised two paths theorem).** Let $G$ be a graph with a cycle $C$. The following are equivalent:

* $G$ is a web with frame $C$,

* $G$ is maximally $C$-crossless.

We define a simple operation on webs, which we call *web composition*: two webs can be “glued” along induced subpaths of their frames, resulting in a new web. We shall prove that all webs can be constructed from cliques (with triangles as frames) by successive web compositions. For instance, the ribs from Figure 1 can be constructed as illustrated in Figure 2.

Equipped with this tool, we proceed as follows to prove the difficult implication of the theorem (maximally *C*-crossless graphs are webs with frame *C*). Suppose *C* = $x_1x_2y_1y_2x_1$ has size four, the overall process is depicted in Figure 3. At first, we only know that the graph contains *C*: edges in this cycle cannot be used in a crossing. We define a path *P* from $x_1$ to $y_1$, initially composed of neighbours of $y_2$ only, which we transform to make it closer and closer to $x_1x_2y_1$, progressively revealing the web-structure of the starting graph.

At each stage in Figure 3, the bottom-left part of the graph is a web with frame $y_2Py_2$, and the top-right coloured one is a maximally $x_2Px_2$-crossless graph. We process this latter part recursively to obtain a web, and we compose it with the former along the induced subpath *P* to obtain the desired web.

**1.2. Two disjoint paths problem.** The two paths theorem is inherently related to the algorithmic problem of finding vertex-disjoint paths between fixed pairs of vertices of a given graph. This problem has been widely studied in the literature; it is NP-complete on directed graphs [1], and polynomial on undirected graphs [6, 7, 10].
<figure><img src="image_5.png" /><figcaption>FIG. 3. *Recursively revealing the web-structure of a maximally crossless graph.*</figcaption></figure>

Many variations of this problem exist, such as optimisation versions [8], acyclic case [5], etc. We focus on the following variant: given vertices $s_1, t_1, s_2, t_2$ in a simple undirected graph, find vertex-disjoint paths respectively from $s_1$ to $t_1$ and from $s_2$ to $t_2$. If $s_1 = s_2$ or $t_1 = t_2$, then this problem is solved by Menger's theorem: say $s_1 = s_2$; the two paths exist if and only if every vertex separator between $s_1$ and $\{t_1, t_2\}$ has at least two elements. Various methods relating to flow networks exist to solve such a problem. The difficulty arises when $s_1 \neq s_2$ and $t_1 \neq t_2$. The corresponding algorithmic problem is usually called the *two disjoint paths problem*. Menger's theorem would apply to find vertex-disjoint paths between $\{s_1, s_2\}$ and $\{t_1, t_2\}$, but requiring paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively, makes the problem harder.

Since the seminal works in [6, 7, 10], several efficient algorithms have been introduced. For instance, algorithms running in $O(n^2)$, $O(n + m \log n)$, and $O(n + m\alpha(m, n))$ are respectively proposed in [4, 2, 9], where $n$ and $m$ are the number of vertices and edges, respectively, and $\alpha$ is the two parameters variant of the inverse of the Ackermann function. All are based on improving the $O(nm)$ algorithm by Shiloach [7]. The latter relies on a sequence of six reductions, three of which involve previous works: instances can be reduced to the 3-connected case (e.g. using the algorithm from [3] to decompose a graph into its triconnected components), and even the 3-connected non-planar case [5], both in $O(n+m)$ time. By Kuratowski's Theorem the resulting instance contains a topological $K_{3,3}$ or $K_5$. Another reduction allows one to assume that the instance does not contain a $K_5$ [13]. To quote Shiloach "We have not written the solution as an explicit, long, and tedious algorithm".

We use the insights of our proof of the two paths theorem to design a simple $O(nm)$ algorithm for the following slight generalisation of the two disjoint paths problem. Given a tuple $T$ of at least three vertices in a graph $G$, we call *web completion* of $G$ with regard to $T$ a set $F$ of edges such that $G + F$ is a web with frame $T$.

## TWO DISJOINT PATHS OR WEB COMPLETION

**Input:** A graph with a tuple of distinct vertices.

**Output:** A crossing or a web completion.
<figure><img src="image_6.png" /><figcaption>FIG. 4. *A frame-separating path and a completion for it.*</figcaption></figure>

In contrast to Shiloach's method, no reductions are required: our algorithm consists of two procedures of ten lines of pseudo-code each, which are self-contained but for calls to some search algorithm (e.g. depth-first or bread-first).

Its principle, in the decision version of the problem, goes as follows: given a graph $G$ with a tuple of vertices $T$, if there are no paths in $G$ between non-consecutive vertices of $T$, then return No—$T$ is not crossed. Otherwise, compute a path $P$ between non-consecutive vertices of $T$. If $P$ does not separate $T$, then return Yes—$T$ is crossed. Otherwise, $G$ has the shape depicted on the left of Figure 4. Let $T_1$ and $T_2$ be the two parts of $T$ which are separated by $P$. The graphs $G_i$ with tuples $T_i P$ are then used as subinstances for recursive calls.

Applying this process blindly is not sufficient. Indeed the recursive calls may not be safe. More precisely, it is possible that $PT_i$ is crossed in $G_i$ while $T$ is not in $G$ (for some $i \in \{1, 2\}$). To ensure safeness we first compute what we call a *P-completion*. Roughly, this is a set of edges on $P$'s vertices we add to $G$ such that, using these edges, $P$ contains a shorter path $P'$ whose associated subinstances are safe. In the easy cases, computing a $P$-completion corresponds to adding the red dotted edges as on the right of Figure 4. Covering all cases is delicate, but we eventually obtain a simple and efficient procedure for computing $P$-completions.

**1.3. Contributions.** Our three contributions are:

* an inductive characterisation of webs, via web composition (Section 3);

* a direct proof of (a generalisation of) the two paths theorem (Section 4);

* a simple $O(nm)$ algorithm for the two disjoint paths problem (Section 5).

**1.4. Outline.** We fix notations, make the above definitions precise, and provide a few basic observations in Section 2.

We study webs in Section 3. We prove that their frames are crossless (Proposition 3.2) and that they can be generated by repeated web compositions (Proposition 3.6). We provide most details for the sake of completeness, so that this section requires a few pages.

We then move to the proof of the generalised two path theorem, in Section 4. We first prove maximality of webs amongst crossless graphs, which is part of the easy direction in the literature, and which is later instrumental for our algorithm. We finally prove that maximally crossless graphs are webs, which the difficult implication in the works of Thomassen [10] and Seymour [6]. Despite its arrival late in the text, this proof is self-contained: we only need to know from Section 3 that webs are preserved by web composition (Proposition 3.1).

We finally present our algorithm for the two disjoint paths problem, in Section 5.
<figure><img src="image_7.png" /><figcaption>FIG. 5. *The wheel graph* $W_7$ (*left*) and *the fan graph* $F_7$ (*right*).</figcaption></figure>

**2. Definitions.**

**2.1. Standard notations and terminology.** We only consider simple and undirected graphs, with the following conventions. Given a graph $G$, we write $V(G)$ for its set of vertices and $E(G)$ for its set of edges—two-elements sets of vertices. We often use a graph to denote its underlying set of vertices, thus writing $G$ for $V(G)$; similarly, we often write $x$ for the singleton set $\{x\}$. We note $n = |V(G)|$ the order of $G$ and $m = |E(G)|$ the size of $G$. If $G'$ is another graph, then $G \uplus G'$ is the disjoint union of $G$ and $G'$. Given $V \subseteq V(G)$ a subset of vertices, we note $G[V]$ for the subgraph of $G$ induced by $V$, and $G - V$ for the graph $G$ where all vertices of $V$ and incident edges have been removed. An edge subgraph of a graph $G$ is a graph $H$ with $V(H) = V(G)$ and $E(H) \subseteq E(G)$. The set of neighbours of a vertex $x$ in a graph $G$ is denoted by $N_G(x)$. If $F$ is a set of edges on $V(G)$ then $G+F$ is the graph obtained from $G$ by adding the edges in $F$. Given two vertices $x$ and $y$ of $G$, we write $G/xy$ for the identification of $x$ and $y$ in $G$. A walk is a sequence of adjacent vertices; it is a path when no vertices are repeated; it is a cycle if it contains at least three vertices and exactly the first and last elements are repeated. The length of a path or cycle is its size, i.e., its number of edges. An induced path is a path that is induced as a subgraph. Given a walk $P = x_1 \dots x_k$, the interior of $P$ is $\tilde{P} = x_2 \dots x_{k-1}$, and the reversal of $P$ is $\bar{P} = x_k \dots x_1$. Given a second walk $Q = y_1 \dots y_r$ with, say, $x_i = y_j$, we note $Px_iQ$ for the walk from $x_1 \dots x_iy_{j+1} \dots y_r$. If $x_k = y_1$, we simply note $PQ$ for $Px_kQ$. If $P$ and $Q$ are paths, $x_1 = y_r$, and $x_s \neq y_t$ when $1 < s < k$ and $1 < t < r$, then $PQ$ is a cycle.

Given two sets $H, K$ of vertices, a path $P = x_1 \dots x_k$ is an $H$-$K$ path if $x_1 \in H$, $x_k \in K$, and $x_i \notin H \cup K$ for all $1 < i < k$. When $H = K$ we simply say that $P$ is an $H$-path. A third set of vertices $U$ is $H$-connected to $K$ when there is a $H$-path from $U$ to $K$. In this work, disjoint paths always means vertex-disjoint paths. A subset $X$ of vertices separates two sets of vertices $U$ and $V$ when all $U$-$V$ paths contain a vertex of $X$.

We write $K_n$ for the clique of order $n$, i.e, the graph with all edges between $n$ vertices. A universal vertex in a graph is a vertex adjacent to all other vertices. For instance, the centre of a star graph is universal. In addition to the cliques, we define the following standard graph families:

* the wheel graph with $n \ge 4$ vertices is the graph $W_n$ obtained from the cycle of size $n-1$ by the addition of a universal vertex;

* the fan graph with $n \ge 3$ vertices is the graph $F_n$ obtained from the path of order $n-1$ by the addition of a universal vertex.

Examples of a wheel and a fan graph are shown in Figure 5. Observe that if $e$ is an edge in a wheel graph that is not incident to the universal vertex, then $F_n \simeq W_n - e$.
<figure><img src="image_8.png" /><figcaption>FIG. 6. More examples of webs and ribs; dotted red vertices and edges are clique vertices and edges, while black ones are rib vertices and edges. The ribs of the webs on the top part are the only ribs of order three, four, and five.</figcaption></figure>

## 2.2. Generalised ribs and webs.

**DEFINITION 2.1.** Given $k \ge 3$, a *k-rib* is a planar graph such that in one of its plane embeddings, the outer face is a cycle of length *k* called its frame, all inner faces are triangles, and all triangles are inner faces.

A *k-web* is a graph constructed from a *k-rib R* by adding one clique $K_T$ per triangle *T* of R and making vertices of $K_T$ adjacent to the vertices of *T*.

In the sequel, when the size of the frame is not relevant, we often simply call ribs and webs the graphs from this generalised definition. Ribs are particular “near-triangulations of the plane” [12] in which all triangles are faces, and in the literature, webs are exactly the 4-webs. In addition to Figure 1 from the introduction, examples of webs and ribs are depicted in Figure 6.

**PROPOSITION 2.2.** The 3-ribs are the triangles; the 3-webs are the cliques of order at least 3.

**PROPOSITION 2.3.** Let *x* be a vertex in a rib *R* with frame *C*. The subgraph of *R* induced by *x* and $N_R(x)$ is:

* a wheel graph when *x* is not in *C*, or

* a fan graph when *x* is in *C*.

*Proof.* Consider a plane embedding of *R* in which *C* bounds the outer face, all inner faces are triangles, and all triangles are inner faces. Let *H* be the subgraph of *R* induced by *x* and its neighbours. In the embedding of *R*, the edges going out from *x* form a star whose centre is *x*:

<figure><img src="image_9.png" /></figure>
<figure><img src="image_10.png" /><figcaption>FIG. 7. Two examples of crossings (red dashed paths) for some cycles (blue dotted cycles).</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>FIG. 8. Edge composition of two graphs.</figcaption></figure>

Each consecutive pair of edges bounds a common face represented by a coloured area in the drawing above. Either all such faces are inner, meaning are triangles, and $H$ is a wheel graph (and $x$ cannot bound the outer face: $x$ is not on $C$), or some of these faces are the outer face. The outer face being bounded by a cycle $C$, at most two edges incident to $x$ may bound the outer face. In this case $x$ is in $C$ and $H$ is a fan graph. $\square$

**2.3. Crossings.** As explained in the introduction (Section 1.1), the appropriate generalisation of linkages is given by *crossings*:

**DEFINITION 2.4.** Let $T = (x_1, \dots, x_k)$ be a tuple of at least three pairwise distinct vertices in a graph $G$. A crossing of $T$ is a pair of disjoint $T$-paths, from $x_i$ to $x_j$ and $x_r$ to $x_s$, respectively, such that $i < r < j < s$. The tuple $T$ is crossed if it admits a crossing; it is crossless otherwise. The graph $G$ is maximally $T$-crossless when $T$ is crossless and in any edge extension of $G$, $T$ crossed.

Two examples of crossings are given in Figure 7; they are crossings in the bottom ribs of Figure 6 but for a tuple different from their frames.

Observe that a graph is 2-linked precisely when all tuples of four distinct vertices are crossed; therefore, the standard two paths Theorem 1.1 is precisely our generalised Theorem 1.3 when $|C| = 4$. Moreover, in the case where $|C| = 3$, $C$ cannot be crossed, thus Theorem 1.3 holds since 3-webs are cliques by Proposition 2.2.

**3. Web compositions and decompositions.**

**3.1. Edge composition.** The graph operation consisting in taking the disjoint union of two graphs and then identifying two edges $e$ and $e'$, one from each graph, is called *edge composition along* $e$ and $e'$.

Edge composition is illustrated in Figure 8. Edge compositions of webs along edges of their frames always produce webs: plane embeddings can be composed in this way, all triangles remain faces and all inner faces remain triangles. If the identified edges are denoted $e = xy$ and $e' = x'y'$ and the frames of the composed webs are respectively $Pxy$ and $P'x'y'$, then the resulting web has frame $PP'$.

An example is the rib in the bottom right corner of Figure 6: the black dashed edge results from the edge identification in the edge composition of two ribs. Similarly,
<figure><img src="image_12.png" /><figcaption>FIG. 9. Path composition of two ribs. The resulting graph is not a rib (nor a web). Indeed, the dashed red edge, resulting from the collateral identification of the two bended edges on the left, is shared by three triangles; thus, at least one of these triangles cannot be a face in a plane embedding of the path composition.</figcaption></figure>

three of the six ribs from Figure 1 were obtained as edge compositions of ribs.

In contrast, the rib in the bottom left corner of Figure 6, as well as the three other ribs from Figure 1 cannot be expressed as an edge composition of webs.

**3.2. Path composition.** To decompose webs in general (except for the base case of 3-webs, i.e., cliques), we generalise edge composition to identify subpaths of frames instead of single edges.

If $P = x_1...x_l$ and $P' = x'_1...x'_l$ are non-empty paths of length $l$ in two graphs $G$ and $H$, respectively, we define the *path composition* of $G$ and $H$ along $P$ and $P'$ as the graph

$$ (G \uplus H)/x_1x'_1/.../x_lx'_l. $$

When $P = P'$ we simply talk of *path composition along P*.

In the particular case where $P$ and $P'$ are reduced to one edge each, that is $l = 1$, the notion coincides with edge composition.

Unfortunately, path compositions of webs along subpaths of their frames are not always webs (although this is true for edge compositions, as explained above). A counter-example is given in Figure 9; to fix this issue, we have to restrict to induced subpaths of the frames.

**3.3. Web composition.** Let $G$ and $H$ be two webs and let $P$ and $P'$ be subpaths of their respective frames of the same length. If $P$ and $P'$ are induced paths in $G$ and $H$, respectively, we call *web composition of G and H* along $P$ and $P'$ the path composition of $G$ and $H$ along $P$ and $P'$.

Webs are stable under web composition:

**PROPOSITION 3.1.** *The web composition along P and P' of two webs G and H with respective frames $P_G P$ and $P_H P'$, is a web with frame $P_G P_H$.*

*Proof.* Let $R_G$ and $R_H$ be the ribs of $G$ and $H$, respectively, and $R$ the web composition of $R_G$ and $R_H$ along $P$ and $P'$. We prove that $R$ is a rib.

Any planar graph admits a plane embedding for which the outer face is sent exactly onto a given prescribed polygon of the plane (see [11]).

Consider plane embeddings of $R_G$ and $R_H$ for which the outer faces are sent onto two polygons whose intersection is precisely $P$ and $P'$. As $P$ and $P'$ are induced, there are no parallel edges in the union of the plane embeddings of $R_G$ and $R_H$. Hence, this union is a plane embedding of $R$.

As all inner faces of the embedding of $R_G$ or $R_H$ are triangles, so are inner faces of $R$. As $P$ and $P'$ are induced, a triangle of $R$ is either a triangle of $R_G$ or of $R_H$, but not of both. Hence every triangle of $R$ is a face in this embedding. So $R$ is a rib.
Adding back the clique vertices of $G$ and $H$ on their respective triangles gives a web, proving that the web composition of $G$ and $H$ along $P$ and $P'$ is a web with rib $R$ and frame $P_G \overline{P}_H$. $\square$

**3.4. Crossings in webs.** An immediate yet important observation is that in a web with rib $R$, the intersection with $R$ of a path with endpoints in $R$ yields an induced path. Indeed, if such a path $P$ uses a clique vertex $u$, then we can take the longest subpath $Q$ of $P$ containing $u$, and whose inner vertices are all clique vertices. The endpoints of $Q$ are on a triangle $T$ of the rib. In particular $Q$ can be replaced in $P$ by an edge of $T$:

<figure><img src="image_13.png" /></figure>

In this figure the green triangular shape in the centre of the triangle represents all the clique vertices of $T$.

Conversely, induced paths whose endpoints are on the rib are entirely on the rib.

Thomassen's argument [10] proving that frames of 4-webs are not 2-linked, generalises to $n$-webs:

**PROPOSITION 3.2.** *Frames of webs are crossless.*

*Proof.* Suppose by contradiction that the frame of a web is crossed. The union of the frame and the paths from a crossing yields a topological $K_4$. By intersecting paths with the rib, we can assume a topological $K_4$ in the rib. In a planar embedding of the rib in which the frame bounds the outer face, this provides an outerplanar plane embedding of $K_4$, a contradiction. $\square$

**3.5. Edge decompositions.** We characterise when a web with frame $C$ is expressible as the edge composition of two webs using the $C$-connectivity of vertices; we first need the following lemma.

**LEMMA 3.3.** *Let $x$ be a vertex in a web $G$ with frame $C$ such that $|C| \ge 4$. There exists a $C$-path $P$ between non-consecutive vertices $c_x$ and $c'_x$ of $C$ such that $x$ is $C$-connected to all vertices of $P$.*

*Proof.* It is sufficient to prove the statement for ribs. Indeed, except perhaps for its endpoints, we have seen that induced paths in webs are paths in their ribs. Hence, two rib vertices are $C$-connected in $G$ if and only if they are $C$-connected in the rib of $G$; two clique vertices are $C$-connected in $G$ if and only if two of their rib neighbours are $C$-connected in the rib of $G$.

When $x$ is a vertex in $C$, by Proposition 2.3, the neighbourhood of $x$ induces a fan graph $F$. Write $P$ for the path $F - x$ whose endpoints are the predecessor and successor of $x$ on $C$. If $P$ is a $C$-path, then we take the endpoints of $P$ for $c_x$ and $c'_x$; $P$ is a $C$-path from $c_x$ to $c'_x$ whose vertices are all $C$-connected to $x$. If $P$ is not a $C$-path, then $P$ contains a vertex $y$ of $C$ which is adjacent to $x$. Since $y$ is inner in $P$, $x$ and $y$ are non-consecutive on $C$. We take $x$ and $y$ for $c_x$ and $c'_x$, and $Q = c_x c'_x$. The path $Q$ is a $C$-path from $c_x$ to $c'_x$ whose vertices are all $C$-connected to $x$.

Assume that $x$ is not a vertex of $C$. Observe that ribs are connected, and consider an induced $C$-path $P$ from $x$ to a vertex $c$ of $C$. By Proposition 2.3, the neighbourhood of $c$ induces a fan graph in $G$. Hence, this neighbourhood provides paths from the penultimate vertex $u$ of $P$ to the two neighbours $d$ and $d'$ of $c$ on $C$, and these two
<figure><img src="image_14.png" /><figcaption>FIG. 10. The case where $c_x = d$ and $c'_x = d'$ in the proof of Lemma 3.3.</figcaption></figure>

paths $Q$ and $R$ are disjoint except possibly for $u$.

For $c_x$ and $c'_x$ we take the first vertices of $Q$ and $R$ which are on $C$, respectively (see Figure 10 for an illustration when $c_x$ and $c'_x$ are $d$ and $d'$).

All vertices of $Q$ and $R$ are neighbours of $c$. For the sake of contradiction, suppose that $c_x$ and $c'_x$ are consecutive on $C$; $c_x c'_x c_x$ is a triangle of $R$, and hence an inner face. The edge $cc_x$ bounds at least three faces in the plane embedding of $R$ in which the outer face is bounded by $C$, all inner faces are triangles and all triangles inner faces. In a plane embedding of a planar graph, an edge may bound at most two faces, a contradiction.

The paths $PuQ$ and $PuR$ are $C$-paths from $x$ to $c_x$ and to $c'_x$, respectively. They induce a $C$-path from $c_x$ to $c'_x$ whose vertices are all $C$-connected to $x$. $\square$

Thanks to the previous lemma, we can prove the following characterisation. The second and third items in the proposition are refinements of the first one, which are useful in the sequel. We may observe how this characterisation applies to the webs presented in Figures 1 and 6.

**PROPOSITION 3.4.** Let $G$ be a web with frame $C$. The following holds:

1. $G$ is the edge composition of two webs if and only if there is a pair of vertices of $G$ which are not $C$-connected.

2. for all vertices $x, y$, either $x$ is $C$-connected to $y$, or there exists a pair of vertices $c, c' \in C - x - y$ separating $x$ from $y$ and such that $G$ is the edge composition of two webs along $cc'$,

3. for every vertex $x$ and every subpath $P$ of $C$, either $x$ is $C$-connected to $P$, or there are vertices $c, c'$ of $C - P - x$ separating $x$ from $P$ and such that $G$ is the edge composition of two webs along $cc'$.

*Proof.* The first item of the statement is a direct consequence of the second one, which we prove now.

Let $G$ be a web with frame $C$ and two vertices $x$ and $y$ which are not $C$-connected.

By Proposition 2.2, all pairs of vertices in 3-ribs with frames triangles $T$ are $T$-connected. Hence we assume $|C| \ge 4$.

By Lemma 3.3, $x$ is $C$-connected to at least two distinct non-consecutive vertices $c_x$ and $c'_x$ of $C$. Write $Q$ for a $C$-path from $c_x$ to $c'_x$ containing vertices all $C$-connected to $x$. Let $P$ and $P'$ be the two paths from $c_x$ to $c'_x$ such that $PP' = C$.

We prove that the vertices of $C$ which are $C$-connected to $y$ are either all on $P$ or all on $P'$. For the sake of contradiction, suppose that $y$ is $C$-connected to inner vertices $c_y$ and $c'_y$ of $P$ and $P'$, respectively. Define a $C$-path $R$ from $P$ to $P'$ as follows:
• when $y$ is not on $C$, $R$ is a $c_y-c'_y$ path containing only vertices $C$-connected to $y$,

• when $y$ is on $C$, we assume without loss of generality that $y$ is an inner vertex of $P$. For $R$ we take a $y-c'_y$ path.

Since $x$ and $y$ are not $C$-connected, $Q$ and $R$ are disjoint and $(Q, R)$ is a crossing of $C$, a contradiction.

Hence, we assume that the vertices of $C$ to which $y$ is $C$-connected are all on $P$, and without loss of generality, we assume that $P$ is of minimum length such that its endpoints $c_x$ and $c'_x$ are $C$-connected to $x$ and all vertices $C$-connected to $y$ are on $P$.

We chose $c = c_x$ and $c' = c'_x$. We prove that $\{c, c'\}$ separates $\tilde{P}$ from $\tilde{P}'$. For the sake of contradiction, let $R$ be a $C$-path from $\tilde{P}$ to $\tilde{P}'$. Since $x$ is not $C$-connected to $\tilde{P}$, the vertices of $R$ are not $C$-connected to $x$ either. Recall that $Q$ is a $C$-path from $c$ to $c'$ whose vertices are all $C$-connected to $x$. The pair $(Q, R)$ is a crossing of $C$, a contradiction.

Because $\{c, c'\}$ separates $\tilde{P}$ from $\tilde{P}'$, a plane embedding of the rib of $G$ in which the outer face is bounded by $C$, all inner faces are triangles and all triangles are inner faces, has the left-hand side shape below:

<figure><img src="image_15.png" /></figure>

Without being too formal on the manipulation of such embeddings, the green area must correspond to an inner face of the embedding, meaning a triangle. This face being incident to both $c$ and $c'$, that implies that $cc'$ is an edge of $G$. The fact that the rib of $G$ is given by an edge composition of two ribs along $cc'$ is then direct by looking at the inner faces and triangles of $H$ and $K$. Hence, $G$ is an edge composition of $H$ and $K$ in which the clique vertices are restored.

We prove that $\{c, c'\}$ separates $x$ from $y$. For the sake of contradiction, let $R$ be an $x-y$ path in $G - c - c'$. Since $x$ and $y$ are not $C$-connected, $R$ contains at least one vertex of $C$. Write $c_1, \dots, c_n$ for the vertices of $R$ which are vertices of $C$: $R = Rc_1Rc_2\dots c_nR$. Since $x$ and $y$ are not $C$-connected to $\tilde{P}$ and $\tilde{P}'$, respectively, we have that $c_1$ and $c_n$ are on $\tilde{P}'$ and $\tilde{P}$, respectively. Hence, there exists an index $i$ such that $c_i$ is on $\tilde{P}'$ and $c_{i+1}$ on $\tilde{P}$. The path $c_iRc_{i+1}$ is a $C$-path from $\tilde{P}'$ to $\tilde{P}$ in $G - c - c'$, a contradiction.

The last item is proved along the same lines, replacing $y$ with a subpath of $C$. $\square$

**COROLLARY 3.5.** In a web whose frame $C$ has length at least four, there is a $C$-path whose endpoints are non-consecutive vertices of $C$.

*Proof.* As $|C| \ge 4$, consider two non-consecutive vertices $c, c'$ of $C$. If $c$ is $C$-connected to $c'$ then this provides a $C$-path whose endpoints are non-consecutive vertices of $C$. Otherwise, by Proposition 3.4, the web is given as an edge composition along some edge $uu'$ between nonconsecutive vertices of $C$. This edge is a $C$-path whose endpoints are non-consecutive vertices. $\square$

**3.6. Web decompositions.** While the bottom-left web in Figure 6 and the third and sixth ribs in Figure 1 do not arise as edge compositions, they can be expressed as web compositions. In fact, we have the following decomposition result:

**PROPOSITION 3.6.** Every web whose frame has length at least four is a web composition of two webs.
*Proof.* Let $G$ be a web with rib $R$ and frame $C$ with $|C| \ge 4$. By Corollary 3.5 there is a $C$-path $P$ whose endpoints are non-consecutive vertices of $C$. We may assume without loss of generality that $P$ is an induced path, i.e., a path in $R$. Considering a plane embedding of the latter, the path $P$ separates $R$ into two planar graphs whose outer faces are bounded by the two cycles distinct from $C$ and induced by $C$ and $P$, all their faces are faces of $R$ and hence triangles, and all their triangles are triangles of $R$ and hence faces: those two planar graphs are ribs. Adding back the clique vertices of $G$ on their respective triangles, the resulting pair of webs generate $G$ by taking their web composition along $P$. $\square$

Altogether, Propositions 2.2, 3.1, and 3.6 show that the webs are precisely those graphs obtained by repeated web compositions, starting from cliques of order at least three (whose frames are any triangle). Note that such decompositions are not unique in general.

**4. Two paths theorem.**

We now prove the generalised two paths theorem (Theorem 1.3). We have already seen that web frames are crossless (Proposition 3.2); we first show that the webs are maximally so. The proof of this result will be reused to exhibit crossings in our presentation of the algorithm for the two disjoint paths problem (Section 5.3).

**LEMMA 4.1.** *The frame of a web $G$ is crossed in all edge extensions of $G$.*

*Proof.* We reason by induction on the order of $G$. Let $C$ be the frame of $G$. Since 3-webs are cliques (Proposition 2.2) they cannot be extended with a new edge. We may thus assume $|C| \ge 4$, and hence by Proposition 3.6, that $G$ is the web composition of two webs $H$ and $K$ along some induced $C$-path $P$ of $G$. Let $C_H$ and $C_K$ be the frames of $H$ and $K$, respectively. By induction hypothesis, $C_H$ (resp. $C_K$) is crossed in any edge extension of $H$ (resp. $K$).

Let $e = xy$ be an edge which is not in $G$. We prove that $C$ is crossed in $G + e$. To build such a crossing we will rely on the following claim:

**CLAIM 4.2.** *Every vertex of $H$ is $C_H$-connected to $C_H - P$ in $H$, and similarly in $K$.*

*Proof.* As $P$ is induced in both $H$ and $K$, these webs cannot be expressed as some edge composition along some edge between non-consecutive vertices of $P$. The claim follows by the third item of Proposition 3.4 $\prec$

Assume that $x$ and $y$ are in $H - P$ and $K - P$, respectively. As $x$ is $C_H$-connected to $C_H - P$ in $H$ and $y$ is $C_K$-connected to $C_K - P$ in $K$, we can assume to have an $x$-$(C_H - P)$ (resp. $y$-$(C_K - P)$) path $P_x$ in $H$ (resp. $P_y$ in $K$) disjoint from $P$. The pair $(P_x e P_y, P)$ is a crossing of $C$ in $G + e$.

Otherwise $e$ has both its endpoints in either $H$ or $K$, say in $H$. By induction hypothesis, let $(P_1, P_2)$ be a crossing of $C_H$ in $H + e$. We reason by case analysis depending on which endpoints of $P_1$ and $P_2$ are on $P$. Up-to symmetries between $P_1$ and $P_2$, there are five cases, represented in Figure 11 with the shape of the crossing of $C$ we build in $G + e$. The first three cases, in which both $P_1$ and $P_2$ have at least one end not on $P$ are self-explanatory and just require the use of $P$ to extend $P_1$ and/or $P_2$ to form a crossing of $C$ in $G + e$.

In the fourth case of Figure 11, if the end of $P_1$ which is on $P$ is denoted by $z$, then, since $z$ is $C_K$-connected to $C_K - P$ in $K$, there exists a $z$-$(C_K - P)$ path $P'$. Without loss of generality, assume that $P_2$ is from $x$ to $y$; the pair $(P x P_2 y P, P_1 z P')$ is a crossing of $C$ in $G + e$.
<figure><img src="image_16.png" /><figcaption>FIG. 11. The five subcases in the proof of Lemma 4.1 (top), with crossings of the outer cycle we deduce in each case (bottom).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIG. 12. First case in the proof of Lemma 4.3; $x$ and $x'$ are not $C$-connected, $P$ and $P'$ both end at $w$ and $w'$. We eventually obtain the edge composition on the right.</figcaption></figure>

In the fifth case, we first observe that $P_1$ and $P_2$ cannot be reduced to edges as $P$ is induced. All their inner vertices being $C_H$-connected to $C_H - P$, consider an associated path $P'$. Up-to replacing $P'$ by its subpath starting at the last vertex of either $P_1$ or $P_2$, we get, say, a $(C_H - P)-\tilde{P}_1$ path inner disjoint from $P_1$, $P_2$, and $C_H$. Denote it by $P'$ with $u$ its end on $P_1$. If $z$ is the end of $P_1$ that is surrounded by $P_2$'s endpoints on $P$, then just as above we get a $z$-$(C_K - P)$ path $P''$ in $K$ that is inner disjoint with $C_K$. Without loss of generality, assume that $P_2$ is a path from $x$ to $y$; $(P'uP_1zP'', PxP_2yP)$ is a crossing of $C$ in $G + e$. $\square$

We finally prove the direct implication of the two paths theorem, which is the difficult one in the literature.

**LEMMA 4.3.** Let $G$ be a graph with a cycle $C$. If $G$ is maximally $C$-crossless, then $G$ is a web with frame $C$.

*Proof.* Let $G$ be a maximally $C$-crossless graph for a cycle $C$. Edges of $C$ cannot be used in crossings, so that $C$ must be a subgraph of $G$ by maximality. We proceed by induction on $|G|$ and we perform a case analysis on whether all pairs of distinct vertices of $C$ are $C$-connected or not.

1. There are two vertices $x$ and $x'$ of $C$ which are not $C$-connected

Denote by $y$ and $z$ the two neighbours of $x$ on $C$. Trivially, $x, y, z$ are all $C$-connected to $x$. As $x$ is not $C$-connected to $x'$, we can consider $P'$ the longest portion of $C$ containing $x'$ whose inner vertices are all not $C$-connected to $x$. Let $P$ be the path of $C$ such that $C = PP'$ and call $w, w'$ the shared endpoints of $P$ and $P'$. We are going to prove that $G$ is the edge composition of two webs along $ww'$; this situation is summarised in Figure 12.
<figure><img src="image_18.png" /><figcaption>FIG. 13. Second in the proof of Lemma 4.3, and shape eventually obtained.</figcaption></figure>

To this end, we first prove that that {$w, w'$} separates C. More precisely, that none of the inner vertices u and v, respectively of P and P', are C-connected.

If $u = x$ then inner vertices of $P'$ are not C-connected to $x$ by definition. Thus we assume $u \neq x$. For the sake of contradiction, let $Q$ be a C-path from $u$ to $v$. Let $w$ be the endpoint of $P$ such that $u$ is inner in $wP_x$, and let $w'$ be the other end of $P$. By minimality of $P$, there exists an $x-w$ path $R$ inner disjoint from $C$. If $Q$ and $R$ were not disjoint, then they would induce an $x-v$ path inner disjoint from $C$, a contradiction. Otherwise, $(Q, R)$ is a crossing of $C$ in $G$, a contradiction.

Thus {$w, w'$} separates C. In particular adding the edge $ww'$ cannot create a crossing of C in G, so that by maximality, this edge must belong to G. Hence, G is the edge composition of two graphs along $ww'$, respectively containing P and $P'$. Quite directly, these two graphs are maximally crossless for $Pww'$ and $P'ww'$, respectively. By induction hypothesis they are webs and, by Proposition 3.1, G is a web.

## 2. All pairs of distinct vertices of C are C-connected

Take consecutive vertices $x, y, z$ on $C$ with an $x-z$ path $P$ inner disjoint from $C$. For such a path $P$ we write $C_C^P$ for the component of $C - \{x, y, z\}$ in $G - P$. We assume that $P$ is minimal with regard to the measure

$$ \mu(P) = (|G| - |C_C^P|, |P|) $$

where the order on $N \times N$ is the lexicographic product of the usual order $<$. Said otherwise we choose $P$ to maximise the order of the component of $G - P$ containing $C - \{x, y, z\}$ while minimising the length of $P$. In particular, $P$ is induced.

Take $u$ an inner vertex of $P$. We prove that $u$ is $C \cup P$-connected to $C - \{x, y, z\}$. For the sake of contradiction, assume not. We build a crossing of $C$ in $G$.

Let $v, w \in P$ be such that $vPw$ is the longest subpath of $P$ containing $u$ as an inner vertex and whose inner vertices are all not $C \cup P$-connected to $C - \{x, y, z\}$. As $P$ is induced and as $vPw$ contains at least $u$ as an inner vertex, $G$ does not contain $vw$.

Consider $G + vw$. By maximality of $G$, $C$ is crossed in $G + vw$. Let $(P_1, P_2)$ be a crossing of $C$ in $G + vw$, with, say, $vw \in E(P_1)$. The path $P_2$ must contain some inner vertex of $vPw$ as otherwise $(P_2, P_1vPwP_1)$ would be a crossing of $C$ in $G$.

One end of $P_2$ at least must be on $C - y$. Without loss of generality, assume this is the case of its last vertex. Let $s$ be the last vertex in $vPw$ seen by $P_2$. As the last vertex of $P_2$ is on $C - y$, and since $s$ is not $C \cup P$-connected to $C - \{x, y, z\}$, $sP_2$ must either intersect $P$ at one of its inner vertex $t$, or its last vertex is $x$ or $z$. In any case, there is a vertex $t$ of $sP_2$ appearing on $P$, after $s$. This situation is depicted on the left of Figure 13.
By maximality of $s$ it must be outside of $vPw$, providing an $s-t$ path $Q$ such that either $v \in sPt$ or $w \in sPt$. But then, $P$ can be replaced by $PsQtP$ giving a path with lower measure $\mu$ as $C_C^{PsQtP}$ contains $v$ or $w$ on top of all vertices of $C_C^P$. This is a contradiction.

The fact that all inner vertices of $P$ are $C \cup P$-connected to $C - \{x, y, z\}$ has the following implication: components of $G - P - y$ that are incident to $y$ are incident to at most two vertices of $P$ and those are consecutive in $P$. Indeed if such a component could join two non-consecutive vertices $s$ and $t$ of $P$ in a $C \cup P$-path $Q$ not intersecting $C_C^P$, then $PsQtP$ would give a better path than $P$ with regard to the measure $\mu$. Said otherwise, we have proved that $G$ has the shape depicted on the right of Figure 13.

In other words, $G$ is the path composition along $P$ of an edge subgraph of a web (made of the green triangular shapes and whose rib is a fan graph) with frame $zyxP$ with a graph $H$ (the orange area above the triangular shapes) containing $PzCx$ as a cycle. It is easily proved that $PzCx$ is crossed in any edge extension of $H$, hence $H$ is a web with frame $PzCx$ by induction. By Proposition 3.1, since $G$ is the path composition along an induced path of $H$ and an edge subgraph of a web, $G$ is an edge subgraph of a web with frame $C$. By maximality of $G$ and Lemma 4.1, $G$ is a web with frame $C$. $\square$

Combining Lemmas 4.1 and 4.3 with Proposition 3.2, Theorem 1.3 is proved.

## 5. Two disjoint paths problem.

We now turn to the algorithmic problem of finding two disjoint paths. Let $G$ be a graph with a tuple $T$ of pairwise distinct vertices. A web completion is a set $F$ of edges such that $G+F$ is a web with frame $T$. By Theorem 1.3, web completions exist if and only if $T$ is crossless; we solve the following:

### TWO DISJOINT PATHS OR WEB COMPLETION

**Input:** A graph with a tuple of distinct vertices.

**Output:** A crossing or a web completion.

In the next two sections we only consider the decision version of this problem. We discuss the actual computation of crossings and web completions in Section 5.3, and algorithmic complexity in Section 5.4.

**5.1. Method.** Let us abstract the two main cases in the proof of Lemma 4.3: given a graph which is maximally crossless for a cycle $C$, we find an induced $C$-path $P$ which separates $C$ into two paths $P_1$ and $P_2$ corresponding to two components $V_1$ and $V_2$ of $G-P$; up to some assumptions on $P$, the graphs $G[V_1 \cup P]$ and $G[V_2 \cup P]$ are maximally crossless and we conclude by induction.

We turn this inductive argument into a recursive algorithm for finding crossings. The minimality assumption on the separating path in the proof of Lemma 4.3 (in particular with respect to the measure $\mu$) is not suitable to get an efficient algorithm; the difficulty is thus to find a separating path with good enough properties.

Henceforth we assume a graph $G$ with a tuple $T = (x_1, \dots, x_k)$ of distinct vertices. A set of edges $F$ is called *safe* for $T$ if, when $T$ is crossed in $G+F$, then $T$ is crossed in $G$. If $T$ is crossed then all sets of edges are safe; moreover the edges $x_i x_{i+1}$ ($1 \le i \le k-1$) and $x_k x_1$ are all safe for $T$ since they cannot be used in a crossing. Hence we assume that $T$ induces a cycle $C$ in $G$.
<figure><img src="image_19.png" /><figcaption>FIG. 14. A graph and its only web completion (with respect to the outer 4-cycle).</figcaption></figure>

We use the following divide-and-conquer strategy:

• if all *C*-paths of *G* are between consecutive vertices of *C* then *C* is crossless;

• if there is a *C*-path *P* between non-consecutive vertices of *C* such that *C* − *P* is connected in *G* − *P*, then *C* is crossed;

• otherwise, use a separating *C*-path between non-consecutive vertices of *C* to
find two graphs *G*₁ and *G*₂ with cycles *C*₁ and *C*₂ such that:

- *G* is the path composition of *G*₁ and *G*₂ along *P*, and

- *C* is crossed in *G* if and only if *C*₁ is crossed in *G*₁ or *C*₂ is crossed in *G*₂.

Solve the corresponding subinstances recursively, and answer accordingly.

To obtain the two subinstances, we first prove the following proposition.

PROPOSITION 5.1. Let $P$ be a $C$-path of $G$ between non-consecutive vertices of $C$, and let $P_1$ and $P_2$ be the two distinct subpaths of $C$ sharing their endpoints with $P$ and such that $C = P_1 \overline{P_2}$.

If $P$ separates $\vec{P}_1$ from $\vec{P}_2$ then $P_1$ and $P_2$ are contained in subgraphs $G_1$ and $G_2$ of $G$, respectively, and $G$ is the path composition of $G_1$ and $G_2$ along $P$.

Proof. Observe that $\vec{P}_1$ and $\vec{P}_2$ are both non-empty as the endpoints of $P$ are non-consecutive on $C$. The statement follows by studying components of $G-P$. Any such component containing vertices of $\vec{P}_i$ is associated to $G_i$. All other components as well as edges between non-consecutive vertices of $P$ are arbitrarily distributed between $G_1$ and $G_2$. The graph $G_i$ is defined as the subgraph of $G$ induced by the union of $P$ with the components of $G-P$ associated with $G_i$ to which any edge between non-consecutive vertices of $P$ it is not associated with is removed. The fact that $G$ is indeed the path composition of $G_1$ and $G_2$ along $P$ follows easily from $P$ being a separator of $\vec{P}_1$ and $\vec{P}_2$. $\square$

Following the divide-and-conquer strategy described above, the pairs $(G_i, C_i)$
(with $C_i = P_i P$) are regarded as subinstances. Unfortunately, in general it is false
that $C_1$ or $C_2$ is crossed (resp. in $G_1$ or $G_2$) if and only if $C$ is crossed in $G$.

The left-hand side example of Figure 14 shows a graph *G* given as the path
composition of two graphs *G*₁ and *G*₂, each corresponding to a coloured area of the
drawing (two edges do cross so this is indeed a drawing and not a plane embedding).
The path *P* is the one in the intersection of the two graphs. The cycle *C* is the outer
4-cycle. The cycle *C*₁ is crossed in *G*₁ while *C* is crossless in *G*. On the right-hand side
of Figure 14 we have displayed the only web completion of *G* (see how it can be built
by adding one clique of order two on some triangle of the only rib of order five with
a frame of length four in Figure 6). It cannot be expressed as the path composition
of two graphs along *P*: the subinstances induced by *P* in *G* do not behave well with
regard to web completions.

Our solution consists in ensuring a connectivity property on P. Given $i \in \{1, 2\}$,
we say that a vertex $y \in P$ is on $P$-side $i$ when $y$ and $\tilde{P}_i$ are $P$-connected. We refine the previous proposition as follows:

**PROPOSITION 5.2.** Let $P$ be a $C$-path of $G$ between non-consecutive vertices of $C$, and let $P_1$ and $P_2$ be the two distinct subpaths of $C$ sharing their endpoints with $P$ such that $C = P_1\overline{P_2}$.

If $P$ separates $\tilde{P}_1$ from $\tilde{P}_2$ and all vertices of $P$ are on both $P$-sides, then $C$ is crossed in $G$ if and only if $P_1P$ is crossed in $G_1$ or $P_2P$ is crossed in $G_2$, where $G_1$ and $G_2$ are the subgraphs obtained by Proposition 5.1.

*Proof.* Suppose that $\tilde{P}_1$ and $\tilde{P}_2$ are separated by $P$, and that all vertices of $P$ lie on both $P$-sides. We prove the contrapositives of both implications.

* Assume that $P_iP$ is crossless in $G_i$ for every $i \in \{1,2\}$. By Theorem 1.3, $G_i$ has a web completion $F_i$.

In $G_i+F_i$, the path $P$ must be induced. Indeed, if $xy$ were an edge of $G_i+F_i$ between non-consecutive vertices of $P$, then we could consider $z$ an inner vertex of $xPy$. As $z$ is on both $P$-sides, there is in $G_i$ a $\tilde{P}_i$-$z$ path $Q$. The pair $(Q,xy)$ is a crossing of $P_iP$ in the web $G_i+F_i$, a contradiction.

By Proposition 3.1 the web composition of $G_1+F_1$ and $G_2+F_2$ along $P$ is a web, proving that $G$ has a web completion in the form of $F_1 \cup F_2$, and as a consequence of Theorem 1.3 that $C$ is crossless.

* Suppose $C$ is crossless in $G$, and consider a component $D$ of $G-P$ containing vertices of neither $P_1$ nor $P_2$. It is incident to at most two vertices of $P$ and these must be consecutive. Indeed, if that was not the case, then $D$ would induce an $x-y$ path $Q$ between non-consecutive vertices of $P$. Let $z$ be an inner vertex of $xPy$. As $z$ is on both $P$-sides, there are $\tilde{P}_1$-$z$ ad $z$-$\tilde{P}_2$ paths $R$ and $S$ inner disjoint with $C$, $P$, and $Q$. The pair $(PxQyP, RS)$ is a crossing of $C$ in $G$, a contradiction.

The same method works when $D$ is replaced with an edge between non-consecutive vertices of $P$. In particular, $P$ is induced in $G$.

Let $\mathcal{D}$ be the set of all components of $G-P$ containing vertices of neither $P_1$ nor $P_2$. $C$ is crossless in $G-\mathcal{D}$, so by Theorem 1.3 we let $F$ be an associated web completion. As edges between non-consecutive vertices of $P$ make $C$ be crossed, $P$ remains induced in $(G-\mathcal{D})+F$. Hence $P$'s vertices are all in the rib of $(G-\mathcal{D})+F$. This gives webs $H_i$ with frames $P_iP$ such that $(G-\mathcal{D})+F$ is their web composition along $P$. Obviously $H_i$ is a web containing $G_i-\mathcal{D}$. For each component $D$ of $\mathcal{D}$ incident to, say, an edge $xy$ of $P$, if its vertices are in $G_i$ then we make them all into a clique, and adjacent to all vertices of the triangle of $H_i$'s rib containing $xy$ and of the clique of this triangle.

This construction provides a web completion of both $G_1$ and $G_2$ proving that $P_1P$ and $P_2P$ are crossless, respectively in $G_1$ and $G_2$. $\square$

The example of Figure 14 however provides a graph where no $C$-path $P$ may be used to apply this proposition and get two subinstances. We prove that we can always add edges so that we can eventually apply this proposition.

Given a $C$-path $P$ of $G$ we call $P$-completion a safe set $F$ of edges such that $P+F$ contains a $C$-path $P'$ whose vertices are all on both $P'$-sides in $G+F$.

**PROPOSITION 5.3.** Let $G$ be a graph with a cycle $C$. For every $C$-path $P$ between non-consecutive vertices of $C$, there exists a $P$-completion.

*Proof.* Assume $P = y_1 \dots y_l$. If $C$ is crossed in $G$ then $y_1y_l$ is a $P$-completion. If instead $C$ is crossless, then by Theorem 1.3 there is a set $F$ of edges such that $G+F$
<caption>**Algorithm 5.1** General method for the two disjoint paths decision problem.</caption>

1: **procedure** 2DP*(G, C)*   ▷ decides if C is crossed in G or not
2:   **if** there are no C-paths between non-consecutive vertices of C **then**
3:     **return** False
4:     **else**
5:         P ← a C-path between non-consecutive vertices of C
6:         **if** P does not separate C in G **then**
7:             **return** True
8:             **else**
9:                 G, P ← **P-completion**(G, C, P)
10:             **else**
11:         **return** (2DP*(G₁, C₁)* ∨ 2DP*(G₂, C₂*))

<figure><img src="image_20.png" /><figcaption>FIG. 15. Intuition on how *P*-completions are computed.</figcaption></figure>

is a web. Any C-path $P'$ of $G+F$ which is induced and contained in $P+F$ can then be used to prove that $F$ is a $P$-completion (see Claim 4.2 for details on proving that vertices of $P'$ lie on both $P$-sides). □

Equipped with these tools, we introduce our general method in Algorithm 5.1. We assume that a call to **P-completion**(G, C, P) computes a P-completion F with associated C-path P', and returns the pair (G + F, P'). By Proposition 5.2 and induction on the size of the recursive instances, the method is both correct and terminating.

It remains to implement **P-completion**. A naive computation of *P*-completions, along the lines of the proof of Proposition 5.3, amounts to solving the two disjoint paths problem. Our method is only of interest if *P*-completions can be computed efficiently, which is the topic of the next section.

**5.2. Computing P-completions efficiently.** Recall that we are working with a graph G with a cycle C and a C-path P between non-consecutive vertices of C. The goal is to compute a P-completion efficiently. As before we let $P_1, P_2$ be the two distinct subpaths of C with the same endpoints as P and such that $C = P_1\bar{P}_2$.

The core idea behind computing a *P*-completion is to analyse which *P*-sides each vertex of *P* lies on. This reveals some gaps as in the left-hand side graph shape of Figure 15, where the outer cycle is *C*, and the central path with explicit vertices is *P*. At first sight, the red dotted edges form a *P*-completion. The issue is that the red dotted edges may not be well-defined, because there might be components of $G-P$ intersecting neither $\bar{P}_1$ nor $\bar{P}_2$, and also because the gaps may not intersect on vertices which lie on both *P*-sides. The two other graphs of Figure 15 depict two possible choices of red dotted edges in a concrete graph (where *P* is the dashed straight path). In the first one, the right-most red dotted edge is not safe: it makes
the outer cycle crossed. In the second one, the two red dotted edges cannot both be
used in a *C*-path. Our solution, described in Lemma 5.4 below, is to add red edges
one after the other, recomputing sides at each step. On the previous example, we will
obtain that adding one red edge from the last graph (but not both) is enough to get
a *P*-completion.

Write $y_1 \dots y_l$ for $P$. Since $P$ connects non-consecutive vertices of $C$, both $\mathring{P}_1$ and $\mathring{P}_2$ are nonempty. Moreover, as $y_1$ (resp. $y_l$) is adjacent to a vertex of both $\mathring{P}_1$ and $\mathring{P}_2$, $y_1$ (resp. $y_l$) is on both $P$-sides. Hence the following are well-defined: 1. the largest prefix $Py$ of $P$ whose vertices are all on both $P$-sides; 2. when $y \neq y_l$, the first vertex $z$ on $P$ found after $y$ which is on a given $P$-side.

The cornerstone for computing *P*-completions efficiently is the following lemma.
Its proof is involved although the resulting algorithm is quite simple in the end.

LEMMA 5.4. Assume that not all vertices of P lie on both P-sides.

Let $j < l$ be the greatest index such that all vertices of $Py_j$ are on both $P$-sides.

Let $r > j$ be the lowest index such that $y_r$ is on at least one $P$-side.

Let $s \ge r$ be either:

* $s = r$ if $y_r$ is on both $P$-sides, or

* the lowest index such that $y_s$ lies on the opposite $P$-side of $y_r$.

Then the edge $y_j y_s$ is safe, and in the graph $G + y_j y_s$, all vertices of $Py_j y_s$ lie on both $Py_j y_s P$-sides.

*Proof.* To prove that all vertices of $Py_j y_s$ lie on both $Py_j y_s P$-sides in $G + y_j y_s$ we only need proving that $y_s$ is on both $Py_j y_s P$-sides. The remainder follows from the assumption that all vertices of $Py_j$ lie on both $P$-sides in $G$.

Without loss of generality, we assume that $y_r$ is on $P$-side 1 in $G$. The vertex $y_s$ is on $P$-side 2 (we may have $r=s$). These two facts provide a $\mathring{P}_1$-$y_r$ path $Q$ inner disjoint with $P \cup C$ and a $\mathring{P}_2$-$y_s$ path $R$ inner disjoint with $P \cup C$. The paths $R$ and $Qy_rPy_s$ prove that $y_s$ is on both $Py_j y_s P$-sides in $G + y_j y_s$.

We now prove that $y_j y_s$ is safe. If $C$ is crossed in $G$ then it is so in $G + y_j y_s$. Otherwise, $C$ is crossless in $G$ and we prove that it is crossless in $G + y_j y_s$ too. By Theorem 1.3, $G$ has a web completion $F$. Below, we modify $F$ to get a $P$-completion that contains $y_j y_s$, proving this edge is safe for $C$. In $G + F$, we let $P'$ be an induced $C$-path extracted from $P + F$. We first prove four claims relating $P'$ with $P$:

CLAIM 5.5. The edge $y_j y_r$ is safe in $G$.

*Proof.* For the sake of contradiction, let $(Q, R)$ be a crossing of $C$ in $G+y_jy_r$. Since $C$ is crossless in $G$, $(Q, R)$ is not a crossing of $C$ in $G$ and (without loss of generality) $Q$ contains the edge $y_jy_r$. As vertices $y_t$ with $j < t < r$ have no $P$-sides, $\{y_j, y_r\}$ separates them from $C$. Hence, since $R$ has its endpoints on $C$, $R$ does not intersect $y_jPy_r$. The pair $(Qy_jPy_rQ, R)$ is a crossing of $C$ in $G$, a contradiction.

$\triangleleft$

CLAIM 5.6. If some vertex $z$ has $P$-side $i$ in $G$ then it has $P'$-side $i$ in $G+F$.

*Proof.* Indeed, as $V(P') \subseteq V(P)$, a $C \cup P$-path from $z$ to $\mathring{P}_i$ in $G$ is a $C \cup P'$-path from $z$ to $\mathring{P}_i$ in $G+F$.
$\triangleleft$
CLAIM 5.7. All vertices $y_t$ with $1 \le t \le j$ are on $P'$. In particular, the prefix of $P'$ of length $j-1$ is $Py_j$.

*Proof.* For the sake of contradiction, let $y_t$ with $1 \le t \le j$ be a vertex which is not on $P'$. Since $y_t$ is on both $P$-sides, let $Q_1$ and $Q_2$ be $P \cup C$-paths in $G$, respectively from $\tilde{P}_1$ to $y_t$ and from $y_t$ to $\tilde{P}_2$. The pair $(Q_1Q_2, P')$ is a crossing of $C$ in $G+F$, a contradiction.

We prove that the prefix of $P'$ of length $j-1$ is $Py_j$.

For the sake of contradiction, assume that the prefix of $P'$ of length $j-1$ is not $Py_j$ and let $y_a$ be the first vertex on $P'$ such that $P' = Py_a y_{a'} P'$ with $a' \neq a+1$. As $y_{a+1}$ is on both $P$-sides, we can consider $P \cup C$-paths $Q$ and $R$ respectively from $\tilde{P}_1$ to $y_{a+1}$ and from $y_{a+1}$ to $\tilde{P}_2$. The pair $(Q_1Q_2, Py_a y_{a'} P)$ is a crossing of $C$ in $G+F$, a contradiction. $\triangleleft$

CLAIM 5.8. The $j+1$th vertex of $P'$ is a vertex $y_t$ with $j < t \le s$.

*Proof.* For the sake of contradiction, assume not. By Claim 5.7, the $j+1$th vertex of $P'$ is $y_t$ for $t > s$. Since $y_r$ and $y_s$ are respectively on, say, $P$-sides 1 and 2, we can consider $P \cup C$-paths $Q$ and $R$ respectively from $\tilde{P}_1$ to $y_r$ and from $\tilde{P}_2$ to $y_s$. The pair $(Qy_rPy_sR, Py_jy_tP)$ is then a crossing of $C$ in $G+F$, a contradiction. $\triangleleft$

We are now back to proving that $y_j y_s$ is safe. By Claim 5.5 we can assume $r \neq s$, implying, by definition of $r$ and $s$, that $r$ is on exactly one $P$-side in $G$. Without loss of generality, assume $y_r$ is on $P$-side 1 but not 2 in $G$. This implies that $y_s$ is on $P$-side 2 in $G$ and is the only such vertex among $y_{j+1}, \dots, y_s$. Claims 5.7 and 5.8 prove that $P' = Py_j y_t y_{t'} P'$ with $j < t \le s$.

We prove the safeness of $y_j y_s$ by induction on the length of $P'$. If $s=t$ then obviously $F$ contains $y_j y_s$ and this edge is safe. Assume $s-t>0$. It implies that $y_t$ is not on $P$-side 2 in $G$.

The idea of the proof is to use the fact that none of the vertices in $y_{j+1}, \dots, y_t$ lie on $P$-side 2 in $G$ to “cut” some edges of $F$ between these vertices and $P$-side 2, and replace them by an edge closer to $y_j y_s$:

<figure><img src="image_21.png" /></figure>

Assuming this illustration takes the planar embedding of the rib of $G$ into account, adding $y_j y_s$ is safe after the removal of the edges drawn in the middle of the graph on the left hand-side.

This illustration works when $P' = P$ and the vertices in $y_{j+1}, \dots, y_{s-1}$ are directly connected to vertices on $P$-side 2 in $G$ (and hence the edges we remove are all directly incident to vertices in $y_{j+1}, \dots, y_{s-1}$). Neither one of these assumptions hold in general. Instead we prove that $y_j z$ is safe, for $z$ a vertex appearing after $y_t$ on $P'$, allowing us to apply the induction hypothesis on $P' y_j z P'$.

By Proposition 2.3, in $G+F$, $y_t$ and neighbours of $y_t$ that are on $P$-side 2 and on the rib of $G+F$ describe a fan graph:
<figure><img src="image_22.png" /></figure>

In this figure, the green triangles correspond to the clique vertices of the web $G+F$. The path of this fan graph avoiding $y_t$ is a $y_j-y_{t'}$ path $Q$. In what follows we assume we have a plane drawing of $G+F$ which induces a plane embedding of its rib, and such that clique vertices and associated edges of a given triangle of the rib are restricted to the area of the plane bounded by the said triangle.

Let $z$ be an inner vertex of $Q$ on $P$-side 2 in $G$. We prove $zy_t \in F \setminus E(G)$.

Write $u$ and $v$ for the predecessor and successor of $z$ on $Q$, respectively. The edge $y_tz$ is in $F \setminus E(G)$ ($zy_t$ is an edge we want to remove, as explained above), since, together with a $P$-path from $z$ to $\tilde{P}_2$, having $zy_t \in E(G)$ proves that $y_t$ is on $P$-side 2, which is a contradiction in $G$.

We describe a process modifying $F$ to remove $z$ from $y_t$'s neighbours. Remove $y_tz$ from $F$ as well as the edges between clique vertices of the triangles $uzy_t$ and $zy_tv$ of $G+F$'s rib connecting a vertex on no $P$-side and one on $P$-side 2 in $G$. Add the edge $uv$ and fill back the cliques in a compatible way with respect to the new triangles $uzv$ and $uy_tv$. The whole process is represented as follows:

<figure><img src="image_23.png" /></figure>

In this figure, the grey loops are the clique vertices on no $P$-sides in $G$, and the blue thick arcs the ones that have $P$-side 2 in $G$.

The graph obtained at the end of this process is a web. Its rib is induced by the same vertices as the rib of $G+F$. The only possible issue would be that $uv$ is already an edge in $G+F$. That cannot be as then in the drawing of $G+F$ fixed above, $uy_t$ would have been a triangle of the rib while not being an inner face.

We distinguish several cases depending on which $P$-sides in $G$ the inner vertices of $Q$ are on. In the first case, we are able to remove edges in a way close to the illustration provided above, and hence we obtain that $y_jy_t'$ is safe. In the second case, more edges need to be removed to prove that $y_jy_{t''}$ is safe for $t'' \ge t'$.

* All the inner vertices of $Q$ are on $P$-side 2 in $G$; after applying the process above $|Q| - 2$ times, we get a web containing $G$ as well as the edge $y_jy_{t'}$, proving its safeness. In this web the path $P'y_jy_{t'}P'$ is smaller in length than $P'$ allowing us to conclude by induction hypothesis.

* There exists an inner vertex of $Q$ on no $P$-side in $G$; by applying the process above repeatedly, we can assume that all inner vertices of $Q$ have no $P$-side in $G$.

Consider $H$ the maximal (with regard to vertex sets inclusion) connected subgraph of $G+F$ induced by the vertices that are $C \cup P'$-connected to $y_t$, on $P'$-side 2 in $G+F$, as well as on no $P$-side in $G$. All inner vertices of $Q$ are in $H$.
The first vertex of $P'$ that is adjacent to a vertex of $H$ is $y_j$. Indeed, if it was a vertex $y_a$ with $a < j$, then we could consider $P$-paths $Q_1$ and $Q_2$ in $G$ from $\mathring{P}_1$ to $y_j$ and from $y_j$ to $\mathring{P}_2$ respectively and $R$ a $y_a-y_t$ path in $H$, and $(Q_1Q_2, Py_aRy_tP)$ would be a crossing of $C$ in $G+F$, a contradiction.

Let $y_{t''}$ be the last vertex of $P'$ that is adjacent to some vertex of $H$.

We prove that $y_j y_{t''}$ is safe by modifying $F$ in order to add $y_j y_{t''}$. In $G+F$, we remove all edges between vertices of $H$ and vertices of $G+F$ that are not on $P'$. Those are edges between vertices having no $P$-side and on $P$-side 2 in $G$: they are all in $F \setminus E(G)$. Next we add the edge $y_j y_{t''}$. In the plane drawing of $G+F$ we do that close enough to $H$ making it clear that the cycle $y_j P' y_{t''} y_j$ separates vertices of $H$ from the rest of the graph:

<figure><img src="image_24.png" /></figure>

Let $G'$ be the obtained graph. It is clear that $G$ is an edge subgraph of $G'$. We prove that $C$ is crossless in $G'$. By contradiction, assume that $(R, S)$ is a crossing of $C$ in $G'$. One of the paths, say $R$, must contain $y_j y_{t''}$. The path $S$ must contain some vertices of $y_j P' y_{t''}$ as otherwise $(Ry_j P' y_{t''} R, S)$ would be a crossing of $C$ in $G+F$. Let $y_a$ and $y_b$ be the first and last inner vertices of $y_j P' y_{t''} y_j$ appearing on $S$. As the cycle $y_j P' y_{t''} y_j$ separates $H$ from the rest of $G'$, and from $C$ in particular, and as the endpoints of $S$ are on $C$, the path $Sy_a P' y_b S$ does not intersect $H$. Since $H$ is connected we consider a $y_j-y_{t''}$ path $Q'$ such that $\mathring{Q}'$ is a path in $H$. The pair $(Ry_j Q' y_{t''} R, Sy_a P' y_b S)$ is a crossing of $C$ in $G+F$, a contradiction.

Take a web completion of $G'$ and replace the path $P'$ by $P' y_j y_{t''} P'$. The latter is shorter than $P'$, allowing us to conclude by induction hypothesis. $\square$

Thanks to this lemma, we can compute $P$-completions using Algorithm 5.2. Its termination is ensured by the fact that, in the while loop, the length of $P$ is non-increasing while the longest prefix $Py$ of $P$ whose vertices are all on both $P$-sides sees its length increase at each step.

**5.3. Extracting crossings and web completions.** In the previous two sections we have shown how to decide the 2-DISJOINT PATHS OR WEB COMPLETION problem. Now, we show how Algorithm 5.1 can be refined to compute crossings or web completions explicitly. We use the same notations $G, C, P, P_i, G_i, C_i$ as above.

When Algorithm 5.1 returns True we compute a crossing of $C$ as follows:

* if the $C$-path $P$ chosen in $G$ does not separate $C$ then we compute a $\mathring{P}_1-\mathring{P}_2$ path $P'$ in $G-P$ and return $(P, P')$.

* if some recursive call $2DP(G_i, C_i)$ returns True, and hence returns a crossing $(Q, R)$ of $C_i$ in $G_i$, its shape must fall into one of the five cases of Figure 11. The solutions presented there to build a crossing of $C$ in $G$ still work here, thanks to vertices of $P$ being all on both $P$-sides. Returning this crossing then
**Algorithm 5.2 Computing P-completions.**

1: **procedure P-completion(G, C, P)**

2: $P_1, P_2 \leftarrow$ the two subpaths of $C$ separated by $P$ such that $C = P_1 \overline{P_2}$

3: $y \leftarrow$ the first vertex of $P$

4: **while** $y$ is not the last vertex of $P$ **do**

5: $z \leftarrow$ the first vertex of $P$ strictly after $y$ that is on some $P$-side $i$

6: $u \leftarrow$ the first vertex of $P$ after $z$ on $P$-side $j \neq i$

7: $G \leftarrow G + yu$

8: $P \leftarrow PyuP$

9: $y \leftarrow$ the first vertex of $P$ after $y$ whose successor is not on both $P$-sides

10: **return** $G, P$

reduces to computing appropriate $C \cup P$-paths from $Q$ or $R$ to $\tilde{P}_1$ and/or $\tilde{P}_2$.
In the case Algorithm 5.1 returns False, we compute web completions as follows:

* if there are no *C*-paths between non-consecutive vertices of *C*, then each component of *G* − *C* is incident to either one or two vertices of *C*, and in the latter case the two vertices must be consecutive in *C*. We choose $x_0$ in *C* and set $F = \{x_0y \mid y \in V(C), y \neq x_0\} \cup C$. The graph $R = (V(C), F)$ is a *rib* compatible with *G*. For each component of *G* − *C* we choose a triangle of *R* it is incident to. For each triangle *T* of *R* we turn the components of *G* − *C* we associated with *T* into a clique on *T*. This provides a web completion of *G*.

* if both calls **2DP**($G_i$, $C_i$) returned False, and hence a web completion of the graph $G_i$ with respect to $C_i$ for $i \in \{1, 2\}$, then their union is a web completion of $G$ with respect to $C$.

**5.4. Complexity.** Let $G$ be a graph with a cycle $C$ and a $C$-path $P$ between non-consecutive vertices of $C$. To analyse the complexity of the whole algorithm, we need to be more precise about:

* how do we compute paths,

* how do we decide whether a path separates $C$, and

* how do we decide $P$-connectedness and in particular which $P$-sides a given vertex belongs to.

All of these can be done using a *search algorithm* (e.g. depth- or breadth-first searches) forbidding the traversal of some vertices $X \subseteq V(G)$. We call *X-searches* such searches.

Whereas a usual search algorithm allows one to compute the connected components of a graph, *X-searches* allow for the computation of components of $G - X$ as well as the subsets of $X$ these components are incident to.

Let $n = |V(G)|$ and $m = |E(G)|$.

**PROPOSITION 5.9.** *There exists an implementation of Algorithm 5.1 that runs in $O(nm)$ time on connected graphs.*

*Proof.* Let $(G, C)$ be an instance of **2DP** such that $G$ is connected. An $X$-search can be done in $O(m)$ assuming that the relation $- \in X$ is an attribute of vertices of $G$ accessible in constant time. Indeed, this is a simple variation of usual search algorithms.

Beside the call to **P-completion**(G, C, P) the complexity of one recursive call to Algorithm 5.1 lies in four lines: the two **if** statements, the first computation of P, and the computation of the two subinstances. Each can be done in $O(m)$ time by
using either a *C*-search or a *P*-search.

Hence, if *p* is the number of recursive calls made to **2DP** and *K* the complexity of all calls to **P-completion**, Algorithm 5.1 runs in *O(pm + K)*. Each time a new call to **2DP** is made, it means an instance has been divided in two subinstances by finding a *C*-paths *P* separating *C*. It is not difficult to see that the union *C* of all cycles passed as arguments of **2DP** is a planar graph: following the recursive calls, we start with a cycle and we add paths separating inner faces recursively:

<figure><img src="image_25.png" /></figure>

In the figure, the outer cycle is the first cycle *C*, while inner *C*-paths are the recursive separating paths *P* computed in the different calls of **2DP**. The thinner the line the deeper the recursive call.

The number *p* of calls to **2DP** is bounded by the number of edges of this planar graph, meaning *p* = *O(n)*. Hence the complexity of Algorithm 5.1 is *O(nm + K)*.

Finally we look at Algorithm 5.2. It requires one *P*-search at the beginning to compute $P_1$ and $P_2$, as well as one $(C \cup P)$-search for each step of the while loop to compute the *P*-sides each vertex is on. The number of such searches among all calls to **P-completion** in a run of **2DP** is bounded by the sum of *p* with the number of edges added by **P-completion**. Both are bounded by the number of edges in *C* which is a $O(n)$. Hence, $K = O(nm)$ and the complexity of Algorithm 5.1 is $O(nm)$. □

To compute crossings or web completions as described in Section 5.3, the overall complexity is not modified. We have to be careful about how to represent web completions, however.

Indeed, imagine that *most* vertices of *G* are in a component *D* of *G* − *C* that is incident to exactly one vertex of *C* (*n* = |*G*| = *O(|D|*)). If *G* − *D* is a rib, then in any web completion of *G*, all vertices of *D* are in the clique of some triangle of *G* − *D*. This clique contains $\Omega(|D|^2) = \Omega(n^2)$ edges. If *D* is sparse, say it is a tree, then *G* takes only $O(n)$ space in memory to be stored using adjacency lists while all its web completions have $\Omega(n^2)$ edges.

To avoid this problem, instead of representing a web using adjacency lists, we distinguish between rib and clique vertices. The adjacencies between rib vertices are kept in the form of adjacency lists, while the adjacencies of clique vertices are held in the form of the three rib vertices forming their corresponding triangle. As ribs are planar they have $O(n)$ edges. This provides an $O(n)$-space representation of webs in memory.

**Acknowledgements.** The authors would like to thank Stéphan Thomassé for fruitful discussions and for pointing out that an algorithm could hide behind our proof of the two paths theorem.
REFERENCES

[1] S. FORTUNE, J. HOPCROFT, AND J. WYLLIE, *The directed subgraph homeomorphism problem*, Theoretical Computer Science, 10 (1980), pp. 111–121, https://doi.org/10.1016/0304-3975(80)90009-2.

[2] J. GUSTEDT, *The general two-path problem in time o(m log n)*, tech. report, INRIA, 1994.

[3] J. E. HOPCROFT AND R. E. TARJAN, *Dividing a graph into triconnected components*, SIAM Journal on Computing, 2 (1973), pp. 135–158, https://doi.org/10.1137/0202012.

[4] S. KHULLER, S. G. MITCHELL, AND V. V. VAZIRANI, *Processor efficient parallel algorithms for the two disjoint paths problem and for finding a kuratowski homeomorph*, SIAM J. Comput., 21 (1992), pp. 486–506, https://doi.org/10.1137/0221032.

[5] Y. PERL AND Y. SHILOACH, *Finding two disjoint paths between two pairs of vertices in a graph*, J. ACM, 25 (1978), pp. 1–9, https://doi.org/10.1145/322047.322048.

[6] P. D. SEYMOUR, *Disjoint paths in graphs*, Discret. Math., 29 (1980), pp. 293–309, https://doi.org/10.1016/0012-365X(80)90158-2.

[7] Y. SHILOACH, *A polynomial solution to the undirected two paths problem*, J. ACM, 27 (1980), pp. 445–456, https://doi.org/10.1145/322203.322207.

[8] J. W. SUURBALLE AND R. E. TARJAN, *A quick method for finding shortest pairs of disjoint paths*, Networks, 14 (1984), pp. 325–336, https://doi.org/10.1002/net.3230140209.

[9] T. THOLEY, *Solving the 2-disjoint paths problem in nearly linear time*, Theory Comput. Syst., 39 (2006), pp. 51–78, https://doi.org/10.1007/S00224-005-1256-9.

[10] C. THOMASSEN, *2-linked graphs*, Eur. J. Comb., 1 (1980), pp. 371–378, https://doi.org/10.1016/S0195-6698(80)80039-4.

[11] W. T. TUTTE, *Convex representations of graphs*, in Proc. London Math. Soc., vol. 10, 1960, pp. 304–320, https://doi.org/10.1112/plms/s3-10.1.304.

[12] W. T. TUTTE, *On the enumeration of convex polyhedra*, Journal of Combinatorial Theory, Series B, 28 (1980), pp. 105–126, https://doi.org/10.1016/0095-8956(80)90059-3.

[13] M. E. WATKINS, *On the existence of certain disjoint arcs in graphs*, Duke Mathematical Journal, 35 (1968), pp. 231–246, https://doi.org/10.1215/S0012-7094-68-03523-0.