# Deciding the Erdős-Pósa property in 3-connected digraphs

Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva

► To cite this version:

Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva. Deciding the Erdős-Pósa property in 3-connected digraphs. WG 2023 - 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg (CH), Switzerland. hal-04084227

HAL Id: hal-04084227

https://inria.hal.science/hal-04084227

Submitted on 27 Apr 2023

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Deciding the Erdős-Pósa property in 3-connected digraphs*

J. Bensmail¹, V. Campos², A. K. Maia², N. Nisse¹ and A. Silva²

¹ Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France

² ParGO, Universidade Federal do Ceará, Fortaleza, Brazil

**Abstract.** A (di)graph $H$ has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function $f: \mathbb{N} \to \mathbb{N}$ such that, for any $k \in \mathbb{N}$ and any (di)graph $G$, either $G$ contains at least $k$ pairwise vertex-disjoint copies of $H$ as (butterfly) minor, or there exists a subset $T$ of at most $f(k)$ vertices such that $H$ is not a (butterfly) minor of $G - T$. It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property.

**Keywords:** Erdős-Pósa property, Planar digraphs, Butterfly minor.

## 1 Introduction

A classical result by Erdős and Pósa [4] states that there is a function $f: \mathbb{N} \to \mathbb{N}$ such that, for every $k$, every graph $G$ contains either $k$ pairwise vertex-disjoint cycles or a set $T$ of at most $f(k)$ vertices such that $G-T$ is acyclic. The generalization of Erdős and Pósa's result for digraphs and directed cycles was conjectured by Younger [12] and proved by Reed et al. [6].

We say that $H$ is a minor of $G$ if $H$ is obtained from a subgraph of $G$ by a sequence of edge contractions. If $H$ is a digraph and we restrict the contractions in the previous definition to butterfly contractions [5], we get the definition of a butterfly minor. We say that a graph $H$ has the Erdős-Pósa (EP) property for minors if there is a function $f: \mathbb{N} \to \mathbb{N}$ such that, for every $k$, every graph $G$ contains either $k$ pairwise vertex-disjoint copies of $H$ as a minor or a set $T$ of at most $f(k)$ vertices such that $H$ is not a minor of $G-T$. By changing graph into digraph and minor into butterfly minor, the previous definition can

<footnote>* The full versions of omitted or sketched proofs can be found in the appendix.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: The (4 × 4)-grid (left) the (3 × 6)-cylindrical grid $C_{3,6}$ (middle), and the directed wall (right) obtained from $C_{3,6}$ by removing the three red arcs.</figcaption></figure>

be adapted into the *EP property for butterfly minors in digraphs*. In this view, if $H$ is the undirected graph with a unique vertex and a unique loop on it and $D$ is the digraph obtained from $H$ by orienting its loop edge, then Erdős and Pósa proved that $H$ has the EP property for minors while Reed et al. proved that $D$ has the EP property for butterfly minors.

The results of Erdős and Pósa and Reed et al. were generalized by Robertson and Seymour [7] for undirected graphs and by Amiri et al. [1] for digraphs. Robertson and Seymour [7] proved that an undirected graph $G$ has the EP property for minors if, and only if, $G$ is planar. Amiri et al. [1] proved that a strong digraph $D$ has the EP property for butterfly minors if, and only if, $D$ is a butterfly minor of a cylindrical grid (see Figure 1). The results of Robertson and Seymour [7] and Amiri et al. [1] are similar since an undirected graph is planar if, and only if, it is a minor of some grid [8]. Contrary to the undirected case, not all planar digraphs are butterfly minors of a cylindrical grid. In this paper, we provide a structural characterization of planar digraphs that are butterfly minors of a cylindrical grid. In particular, such characterization leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property for butterfly minors.

Although planarity is a necessary condition for a digraph to be a butterfly minor of a cylindrical grid, it is not sufficient. For example, the two planar digraphs of Figure 2 are not butterfly minors of any cylindrical grid. To see this, first note that they are planar, weakly 3-connected, and have essentially a unique (up to the outerface) embedding in the plane, according to Whitney's Theorem [11]. Note also that, in a cylindrical grid, any embedding is such that there is a point in the plane around which all directed cycles go, and in the same direction. We refer to this as being concentric and with same orientation. Now, in the digraph $L$ of Figure 2, the matching between the two directed triangles forces that, in any planar embedding, either the two triangles are not concentric or they have opposite orientations. On the other hand, the digraph $R$ of Figure 2 is acyclic but it is not a minor of any cylindrical grid. To see why, note that, if $R$ was a butterfly minor of a cylindrical grid, then, because $R$ is acyclic, it would also be a butterfly minor of a *directed wall*, which is the digraph obtained by cutting a cylindrical grid along “parallel” arcs (see Figure 1). Note that, in an embedding of a directed wall similar to the one given in Figure 1, no arc goes
<figure><img src="image_3.png" /><figcaption>Fig. 2: Two planar digraphs $L$ (left) and $R$ (right) which are not butterfly minors of any cylindrical grid.</figcaption></figure>

down. This means that some relative positions of the vertices of $R$ in a directed
wall are forced. Namely, the two sources $v_4$ and $v_5$ of $R$ must be below each of
their out-neighbors, vertex $v_1$ must be below its three out-neighbors, and the
universal sink $v_0$ must be above every other vertex. It can then be checked that
these positions must lead to some crossing arcs. This second example shows that
sources and sinks may play an important role in the fact that a planar digraph
may or may not be a butterfly minor of a cylindrical grid. In a way, our main
result tells that the above two examples fully characterize the reasons why a
planar digraph cannot be a butterfly minor of a cylindrical grid.

To formally state our main result, we need a few definitions. Given a digraph
$D = (V, A)$ and $\emptyset \neq X \subset V(D)$, the set of arcs between $X$ and $V \setminus X$ is denoted
by $(X, V \setminus X)$. We say that $(X, V \setminus X)$ is a *dicut* if there are no arcs from $V \setminus X$
to $X$. A *dijoin path* $P$ of $D$ is a directed path in $D$ whose arc-set intersects the
arc-set of every dicut of $D$. A *plane digraph* is a planar digraph together with
a planar embedding. Recall also that, given a plane digraph $H$, $H^*$ denotes its
dual. We can now state our main result.

**Theorem 1.** A digraph *D* is a butterfly minor of a cylindrical grid if, and only if, *D* has a plane spanning supergraph *H* with neither sources nor sinks such that *H*<sup>*</sup> admits a dijoin path.

To get further intuition about Theorem 1, consider the definition of a feedback
arc set $F \subseteq A$ of a digraph $D = (V, A)$, which is any subset of arcs such that
$D-F$ is acyclic. Given a plane digraph $D$, it is known that every directed cycle
of $D$ is associated to a dicut in $D^*$. This implies that a set of arcs is a feedback
arc set of $D$ if, and only if, the corresponding set of its dual edges intersects
the arc-set of every dicut of $D^*$ [2]. Therefore, the fact that $D^*$ admits a dijoin
path means that such path intersects the arcs of a feedback arc set of $D$ "in the
same direction", i.e., intersects the drawing of each directed cycle of $D$, with
each intersection occurring in the same orientation. This is equivalent to being
concentric and with the same orientation. This condition ($D^*$ admits a dijoin
path) allows avoiding the kind of planar digraphs as exemplified by the digraph
$L$ in Figure 2. In turn, the difficulties exemplified in digraph $R$ in Figure 2 are
dealt with by the existence of a supergraph $H$ with neither sources nor sinks.
**Structure of the paper and algorithmic applications.** We first prove that if $D$ is a plane digraph with neither sources nor sinks such that $D^*$ has a dijoin path, then $D$ is a butterfly minor of a cylindrical grid (Theorem 4). Observe that this gives us the sufficiency part of Theorem 1. We then show that if $D$ is a butterfly minor of a cylindrical grid, then $D$ has a planar embedding such that $D^*$ admits a dijoin path (Theorem 5). Observe that $D$ might still have sources and sinks, so the remainder of the proof consists in adding arcs to $D$ in order kill all sources and sinks (Lemma 2).

Theorems 4 and 5 have the following important corollary:

**Corollary 1.** Any digraph $D$ without sources or sinks is a butterfly minor of a cylindrical grid iff $D$ admits a planar embedding s.t. $D^*$ has a dijoin path.

Note that the planar digraph $R$ in Figure 2 is acyclic. So, whatever be its planar embedding, the dual is strongly connected, i.e., $R^*$ has no dicuts. Therefore, every planar embedding of $R$ is such that $R^*$ has a trivial dijoin path (the empty path). Therefore, unfortunately, there is no hope that the condition on sources and sinks can be removed from Corollary 1.

Note that any strongly connected digraph (or strong) $D$ satisfies the conditions of Corollary 1. Together with the result of Amiri et al. [1], this implies that:

**Corollary 2.** Any strong digraph $D$ has the EP property for butterfly minors if, and only if, $D$ admits a planar embedding such that $D^*$ has a dijoin path.

By Whitney's Theorem [11], any weakly 3-connected planar digraph $D$ has a unique (up to the outerface) planar embedding (computable in linear time). Since deciding whether the dual of a plane digraph admits a dijoin path can be done in linear time, then our result has the following algorithmic application:

**Corollary 3.** Deciding whether a weakly 3-connected strong digraph has the EP property for butterfly minors can be done in linear time.

Section 2 is devoted to defining the main notions and to present previously known results used in this paper. Section 3 is devoted to digraphs with neither sources nor sinks. Section 4 is devoted to obtaining the supergraph with neither sinks nor sources.

## 2 Preliminaries

**Planar digraphs and duality.** In this section, we present a number of simple known facts concerning planar graphs and their duals. The interested reader can find formal definitions and proofs for such facts in most books on graph theory (e.g., [10]).

Given a digraph $D = (V, A)$ and $e \in A$, let $D \setminus e = (V, A \setminus \{e\})$ and let $D/e$ be the digraph obtained from $D$ after contracting the arc $e$.

**Observation 1** Let $D = (V, A)$ be a plane digraph, and $e \in A$ be any arc of $D$. Then, $(D \setminus e)^* = D^*/e^*$ and $(D/e)^* = D^* \setminus e^*$.
A *dicut* of a digraph $D = (V, A)$ is a partition $(X, V \setminus X)$ of the vertex-set such that $X$ is a non empty proper subset of $V$ and there are no arcs from $V \setminus X$ to $X$. The arc-set of $(X, V \setminus X)$ is the set of arcs from $X$ to $(X, V \setminus X)$. A *dijoin* $X \subseteq A(D)$ of $D$ is a set of arcs intersecting all dicuts' arc-sets of $D$. A *dijoin path* (resp., *dijoin walk*) of $D$ is a dijoin inducing a directed path (resp., directed walk) in $D$. That is, a dijoin path/walk $P$ of $D$ is a directed path/walk whose arc-set intersects the arc-set of every dicut of $D$.

**Observation 2** A digraph $D$ admits a dijoin path if, and only if, the decomposition of $D$ into strongly connected components has a single source component and a single sink component.

**Observation 3** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $e \in A \setminus A(P)$. Then, $P$ is a dijoin path of $D \setminus e$.

**Observation 4** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $e \in A$. Let $P'$ be obtained from $P$ by contracting $e$ if $e \in A(P)$, and $P' = P$ otherwise. Then, $P'$ is a dijoin walk of $D/e$.

**Observation 5** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $v \in V$ be an isolated vertex. Then, $P$ is a dijoin path of $D \setminus v$.

**Observation 6** Every digraph with a dijoin walk admits a dijoin path.

**Butterfly models and cylindrical grids.** We now present the formal definition of butterfly models. Let $G$ and $H$ be two digraphs. A (butterfly) model of $G$ in $H$ is a function $\eta : V(G) \cup A(G) \to S(H)$, where $S(H)$ denotes the set of all subdigraphs of $H$, such that:

- for every $v \in V(G)$, $\eta(v)$ is a subdigraph of $H$ being the orientation of some tree such that $V(\eta(v))$ can be partitioned into $(\{r_v\}, I_v, O_v)$ where

* $\eta(v)[O_v \cup \{r_v\}]$ is an out-arborescence rooted in $r_v$ (thus in which all non-root vertices have in-degree 1), called the *out-tree* of $v$,

* $\eta(v)[I_v \cup \{r_v\}]$ is an in-arborescence rooted in $r_v$ (thus in which all non-root vertices have out-degree 1), called the *in-tree* of $v$;

- for every two distinct $u, v \in V(G)$, $\eta(u)$ and $\eta(v)$ are vertex-disjoint;

- for every $(x, y) \in A(G)$, $\eta(xy)$ is a directed path of $H$ from the out-tree of $x$ to the in-tree of $y$, with internal vertices disjoint from every vertex of $\eta(u)$ for every $u \in V(G)$, and from every internal vertex of $\eta(uv)$ for every $(u, v) \in A(G) \setminus \{(x, y)\}$.

Throughout this work, given a model of $G$ in $H$, we will refer to the arcs $e \in A(H) \cap \bigcup_{f \in A(G)} A(\eta(f))$ as the **blue arcs** of the model, and to the arcs $e \in A(H) \cap \bigcup_{v \in V(G)} A(\eta(v))$ as the **black arcs**. A vertex of $H$ incident to at least one black arc will be referred to as a **black vertex**.
<figure><img src="image_4.png" /><figcaption>Fig. 3: A planar embedding of the cylindrical grid $C_{6,6}$. The red directed path $Q_{6,6}^*$ is the dijoin path defined and used in Section 4.</figcaption></figure>

A model of $G$ in $H$ is minimal if, for every $v \in V(G)$ and for every leaf $w$ of $\eta(v)$, $w$ is incident to some blue arc. Note that, up to removing the leaves that do not satisfy this property from $\eta(v)$, we can always assume to be working on a minimal model.

Butterfly contracting an arc $(u, v) \in A(D)$ of some digraph $D$ consists in contracting the arc $(u, v)$ if $d^-(v) = 1$ or $d^+(u) = 1$. A digraph $G$ is a butterfly minor of some digraph $H$ if $G$ can be obtained from $H$ by deleting arcs, deleting vertices, and butterfly contracting arcs. Note that if $G$ is a butterfly minor of $H$, then $G$ can be obtained by first removing some arcs, then removing isolated vertices, and finally performing butterfly contractions.

**Observation 7** [1] A digraph $G$ is a butterfly minor of some digraph $H$ if, and only if, $G$ has a butterfly model in $H$.

We now deal with cylindrical grids. Let $n, m \in \mathbb{N}^*$. The cyclindrical grid $C_{n,2m}$ can be seen as a set of $n$ concentric directed cycles having the same direction and linked through $2m$ directed paths that alternate directions (see Figure 3). Formally, $C_{n,2m}$ is the digraph with vertex-set $\{(i,j) | 0 \le i < n, 0 \le j < 2m\}$, and with the following arc-set. For every $0 \le i < n$ and $0 \le j < 2m$, we have $((i,j), (i, j + 1 \mod m)) \in A(C_{n,2m})$, and the directed cycle induced by $\{(i,j) | 0 \le j < m\}$ is called the $i^{th}$ column of $C_{n,2m}$. For every $0 \le i < n - 1$ and $0 \le j < m$, we have $((i, 2j), (i + 1, 2j)) \in A(C_{n,2m})$ and $((i, 2j + 1), (i - 1, 2j + 1)) \in A(C_{n,2m})$. Moreover, for every $0 \le j < 2m$, the directed path induced by $\{(i,j) | 0 \le i < n\}$ is called the $j^{th}$ row of $C_{n,2m}$.

Throughout this work, we consider that any $C_{n,2m}$ is embedded in the plane so that its first column coincides with the outerface (see Figure 3). Hence, we may naturally refer to left/right and top/bottom such that the first (last) column is the leftmost (rightmost) and the first (last) row is the bottommost (topmost). The arcs of a column are referred to as *vertical arcs*. Note that all vertical arcs are going up. The arcs of a row are the *horizontal arcs*. Moreover, the arcs of even (resp., odd) rows are horizontal to the right (resp., to the left).
<figure><img src="image_5.png" /><figcaption>Fig. 4: Green rows and columns are added. Blue arcs belong to the images of some arcs of $G$ by $\eta$. Grey subtrees (with black vertices and arcs) are the images of some vertices of $G$ by $\eta$.</figcaption></figure>

Since $C_{n,2m}$ is strong, we get that $C_{n,2m}^*$ is a DAG. Moreover, $C_{n,2m}^*$ has a unique sink $t^*$, corresponding to the outerface of the given embedding of $C_{n,2m}$, and a unique source $s^*$, corresponding to the face of $C_{n,2m}$ bounded by the last column of $C_{n,2m}$. Note that if $P^*$ is any directed path from $s^*$ to $t^*$ in $C_{n,2m}^*$, then $P^*$ is a dijoin path, i.e., it intersects all dicuts of $C_{n,2m}^*$ (or, equivalently, $P^*$ “crosses” all directed cycles of $C_{n,2m}$).

Let $\eta$ be a butterfly model of a digraph $G$ in $C_{n,2m}$. We will deal with $\eta$ through a few operations. Due to lack of space, we only present them informally.

- Adding one column between columns $i$ and $i+1$ in $\eta$ consists in considering the new model $\eta'$ of $G$ in the cylindrical grid $C_{n+1,2m}$ obtained as follows. Roughly, the left part of the model (between columns 0 to $i$) does not change, one new column is added (with abscissa $i+1$), and the right part of the model (between former columns $i+1$ to $n$) is translated by one column to the right. The horizontal arcs of the model that were going from former columns $i$ to $i+1$ are subdivided once, i.e., they are now directed paths that go from column $i$ to column $i+2$. Note that no vertical arcs of the added column belong to the new model $\eta'$ of $D$. See Figure 4 for an illustration.

- Adding two rows between rows $j$ and $j+1$ in $\eta$ consists in considering the new model $\eta'$ of $G$ in the cylindrical grid $C_{n,2(m+1)}$ defined as follows. All the elements of the model below row $j$, or in row $j$, remain the same, all elements of the model above row $j$ are translated up from two rows, and all vertical arcs from former row $j$ to former row $j+1$ are subdivided twice, i.e., they are now vertical directed paths with three arcs from row $j$ to row $j+3$. Note that no horizontal arcs of the two added rows belong to the new model $\eta'$ of $D$. See Figure 4 for an illustration.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Construction of $D_{P^*}(s, t)$. On the left, a dijoin path $P^*$ is represented by dashed red arcs. On the right, the obtained digraph $D_{P^*}(s, t)$ is depicted.</figcaption></figure>

### 3 Digraphs with neither sources nor sinks

Let $D$ be a plane digraph such that $D^*$ has a dijoin path $P^*$ with arcs $(e_1^*, \cdots, e_p^*)$. Let $D_{P^*}(s, t)$ be obtained from $D$ as follows (see Figure 5 to follow the construction). For every $i \in \{1, \cdots, p\}$, let $e_i = (u_i, w_i)$ be the arc of $D$ corresponding to $e_i^*$. Subdivide $e_i$ into three arcs $(u_i, t_i)$, $(t_i, s_i)$, and $(s_i, w_i)$. Then, remove $(t_i, s_i)$, and, for every $i \in \{1, \cdots, p\}$, identify the vertices $t_1, \cdots, t_p$ into one vertex $t$, and the vertices $s_1, \cdots, s_p$ into one vertex $s$. Finally, add an arc from $s$ to $t$. Note that $V(D_{P^*}(s, t)) = V(D) \cup \{s, t\}$ and, for every $v \in V(D)$, the in-degree (resp., out-degree) of $v$ in $D$ is the same as in $D_{P^*}(s, t)$. Since $P^*$ is a dijoin path of $D^*$, the set $\{e_i\}_{i \le m}$ is a feedback arc set of $D$ [2]. Therefore:

**Observation 8** Let $D$ be a plane digraph such that $D^*$ has a dijoin path $P^*$. If $D$ has neither sources nor sinks, then $D_{P^*}(s, t)$ is a planar DAG having $s$ as unique source and $t$ as unique sink.

A *visibility representation* of a graph $G$ is a mapping of $V(G)$ into non-intersecting horizontal segments<fnref n="3" /> $\{h_u\}_{u \in V(G)}$, together with a mapping $\{t_e\}_{e \in E(G)}$ of the edges into vertical segments such that for every $uv \in E(G)$, we get that $t_{uv}$ has endpoints in $h_u$ and $h_v$, and $t_{uv}$ does not cross $h_w$ for every $w \ne u, v$.

**Theorem 2 ([3]).** Every planar graph admits a visibility representation.

Here, we apply the approach presented in [9] to our context in order to obtain a butterfly model of a planar digraph $D$ into a cylindrical grid, if one exists. For this, we slightly adapt their definitions to our purposes.

We consider a visibility representation $(\{h_u\}_{u \in V}, \{t_e\}_{e \in A})$ of $D = (V, A)$ to be drawn on the plane, and, given two horizontal (vertical) segments $s_1, s_2$, we write $s_1 \le s_2$ if the $y$-coordinate (x-coordinate) of $s_1$ is smaller than the one of $s_2$. Now, given a DAG $D = (V, A)$, we say that a visibility representation $(\{h_u\}_{u \in V}, \{t_e\}_{e \in A})$ of $D$ is *increasing* if $h_u \le h_v$ for every arc $(u, v) \in A$ (in other words, the arcs are all directed upwards).

<footnote n="3">³ Here, segment means line segment in the plane.</footnote>
In [9], in order to construct a visibility representation, the authors show that they can obtain an orientation $D$ of a graph $G$ that is acyclic, has exactly one source $s$ and exactly one sink $t$, and $(s,t) \in A(D)$ (they call such a digraph a *PERT-digraph*). After they obtain this orientation, they use a total order $(v_1, \dots, v_n)$ of $V(G)$ that meets the orientation $D$, and then construct a visibility representation such that $s_1 < s_2 < \dots < s_n$, where $s_i$ denotes the $y$-coordinate of $h_{v_i}$, for every $i \in \{1, \dots, n\}$. Observe that, because the order meets the orientation, we get that this is an increasing visibility representation. Their representation also has the property that the $x$-coordinate of arc $(s,t)$ is smaller than the $x$-coordinate of every other edge of $G$. In short, even though they use a different terminology, the results presented in [9] actually show that the theorem below holds. The interested reader can check this is true by observing, in their algorithm W-VISIBILITY, that after they obtain the desired orientation $D$ (line 2), they only work on $D$ itself; also, the increasing order over the $y$-coordinates is ensured in line 5.1 of their algorithm.

**Theorem 3 ([9]).** Let $D$ be a planar DAG with unique source $s$ and unique sink $t$, and such that $(s,t) \in A(D)$. Then, $D$ admits an increasing visibility representation such that each horizontal segment has a distinct $y$-coordinate, and the $x$-coordinate of the segment of $(s,t)$ is smaller than the $x$-coordinate of the segment of every other arc of $D$.

**Theorem 4.** Let $D = (V, A)$ be a digraph without sources or sinks. If $D$ has a planar embedding such that $D^*$ admits a dijoin path $P^*$, then $D$ has a butterfly model in $C_{n,2m}$ for some $n, m \in \mathbb{N}^*$.

*Sketch of the proof.* By Observation 8, $D_{P^*}(s,t)$ is a DAG with a unique source $s$, a unique sink $t$, and $(s,t) \in A(D_{P^*}(s,t))$. By Theorem 3, there exists an increasing visibility representation of $D_{P^*}(s,t)$. Let $V(D_{P^*}(s,t)) = \{s=v_1, \dots, t=v_n\}$ be ordered increasingly according to their $y$-coordinates on the representation and suppose, without loss of generality, that the $y$-coordinate of $h_{v_1} = h_s$ is 0 and the difference between the $y$-coordinates of $h_{v_i}$ and $h_{v_{i-1}}$ is 2 (their value on the constructed increasing visibility representation are all different, so we just need to adjust it). Observe that, in this case, the $y$-coordinate of $h_{v_i}$ is $2i-2$. We will build a model of $D$ in some cylindrical grid as follows.

For each $v_i \in V(D)$ (hence $i \notin \{1, n\}$), let $h'_{v_i}$ be the segment equivalent to $h_{v_i}$, but in the upper row. In other words, $h'_{v_i}$ has $y$-coordinate $2i-1$, and leftmost and rightmost $x$-coordinates equal to the ones of $h_{v_i}$. The idea of the proof is to relate $v_i$ with the path formed by the union of paths associated to $h'_{v_i}$ and $h_{v_i}$ in the cylindrical grid. Since all arcs of $D$ point upwards, we get that the subpath associated to $h'_{v_i}$ (i.e., in row $2i-1$) corresponds to the out-tree of $v_i$, while the subpath associated to $h_{v_i}$ (i.e., in row $2i-2$) corresponds to the in-tree of $v_i$. $\triangleleft$

Note that Theorem 4 allows us to prove the “if” part of Theorem 1.

**Theorem 5.** If a digraph $D = (V, A)$ has a butterfly model in $C_{n,2m}$ for some $n, m \in \mathbb{N}^*$, then $D$ has a planar embedding such that $D^*$ admits a dijoin path.
*Proof.* Consider the planar embedding of $C_{n,2m}$ such that the outerface contains its first column (see Figure 3) and let $P^*$ be any directed path from the single source of $C_{n,2m}^*$ to its single sink. Note that $P^*$ is a dijoin path of $C_{n,2m}^*$.

By Observation 7, $D$ is a butterfly minor of $C_{n,2m}$. Let $s_1, \cdots, s_q$ be the sequence of operations allowing to get $D$ from $C_{n,2m}$ where these operations are ordered in such a way that first arcs are removed, then isolated vertices are removed and, finally, butterfly contractions are performed. For every $0 \le i \le q$, let $G_i$ be the digraph obtained after the $i^{th}$ operation (so $G_0 = C_{n,2m}$ and $G_q = D$). We show, by induction on $0 \le i \le q$, how to obtain a directed path $P_i$ which is a dijoin path of $G_i^*$. In particular, it holds for $i=0$ by taking $P_0 = P^*$.

Let $i \ge 1$. If $s_i$ consists in removing an arc $e_i$ of $G_{i-1}$ then, if $e_i^* \in A(P_{i-1})$, let $P'_i = P_{i-1}/e_i^*$, and let $P'_i = P_{i-1}$ otherwise. By Observations 1 and 4, $P'_i$ is a dijoin walk of $G_i^*$ and, by Observation 6, $G_i^*$ admits a dijoin path $P_i$. If $s_i$ consists in removing an isolated vertex, then, by Observation 5, $P_i = P_{i-1}$ is a dijoin path of $G_i^*$. And if $s_i$ is a butterfly contraction of the arc $e_i \in A(G_{i-1})$, where $e_i^* \notin A(P_{i-1})$, then Observations 1 and 3 ensure us that $P_i = P_{i-1}$ is a dijoin path of $G_i^*$.

So, finally, let us consider the case when $s_i$ consists in butterfly contracting an arc $e_i = (u,v) \in A(G_{i-1})$ such that $e_i^* \in A(P_{i-1})$. Let us assume that $d^-(v) = 1$ (the case when $d^+(u) = 1$ is symmetric). Observe that $d^+(v) > 0$ as otherwise $e_i^*$ would be a loop, contradicting that $P_{i-1}$ is a directed path. Then, let $\{f_1, \cdots, f_q\}$ be the set of out-arcs of $v$ ordered clockwise in the embedding of $D$ in the plane. Then, let $P'_i$ be the directed walk obtained by replacing $e_i^*$ in $P_{i-1}$ by the directed walk consisting of the arcs $f_1^*, f_2^*, \cdots, f_q^*$. Note that $P'_i$ is a dijoin walk in $G_i^*$. Indeed, consider the set of arcs $K$ of a dicut of $G_i^*$. If $K$ is also a dicut in $G_{i-1}^*$, then $e_i^* \notin K$ and $P'_i$ intersects $K$ since $P_{i-1}$ is a dijoin path and so intersects $K$. Otherwise, $e_i^* \in K$ which implies that $\{f_1^*, f_2^*, \cdots, f_q^*\} \cap K \ne \emptyset$, and so $P'_i$ intersects $K$. Finally, by Observation 6, $G_i^*$ admits a dijoin path $P_i$.

□

Theorems 4 and 5 prove the following corollary which corresponds to Theorem 1 in the case of digraphs with neither sources nor sinks (and in particular, Corollary 3 is a special case of the following corollary).

**Corollary 4.** A digraph $D$ without sources or sinks is a butterfly minor of a cylindrical grid if, and only if, $D$ admits a planar embedding such that $D^*$ has a dijoin path. Moreover, if $D$ is weakly 3-connected, then this can be decided in linear time.

*Proof.* Due to the weakly 3-connectivity of $D$, and by Whitney's Theorem, $D$ has a unique (up to the outerface) planar embedding (and a unique dual). Given such an embedding, checking the existence of a dijoin path can be done in linear time by Observation 2. □

Recall that a strong digraph $D$ has the EP property for butterfly minors iff $D$ is a butterfly minor of a cylindrical grid [1]. Together with our result, we get:

**Corollary 3.** Deciding whether a weakly 3-connected strong digraph $D$ has the EP property for butterfly minors can be done in linear time.
# 4 Digraphs with sources and sinks

We have seen that if $D$ is a butterfly minor of a cylindrical grid, then $D$ has a planar embedding such that $D^*$ admits a dijoin path (Theorem 5). As we want to show that this holds for a *spanning supergraph* with neither sources nor sinks, it remains to “kill” sources and sinks in $D$. This is done in this section.

Given a cylindrical grid $C_{n,2m}$ with the canonical planar embedding described previously, let $Q_{n,2m}^*$ be the directed path of the dual $C_{n,2m}^*$ whose arcs correspond exactly to all arcs of $C_{n,2m}$ that go from the last (topmost) row to the first (bottommost) row. Note that $Q_{n,2m}^*$ is a dijoin path of $C_{n,2m}^*$ (see Figure 3). The next lemma states that if a digraph $D$ has a model in a cylindrical grid, then it is possible to get a model such that $Q_{n,2m}^*$ only crosses blue arcs of this model.

**Lemma 1.** If a digraph $D$ has a butterfly model $\eta$ in $C_{n,2m}$, then $D$ has a butterfly model in $C_{n',2m'}$ for some $n' \ge n$ and $m' \ge m$ such that no black arcs of this model are dual of an arc of $Q_{n',2m'}^*$.

**Lemma 2.** If a digraph $D = (V, A)$ has a butterfly model in $C_{n,2m}$, then $D$ has a spanning supergraph with neither sources nor sinks that has a butterfly model in $C_{n',2m'}$ for some $n' \ge n$ and $m' \ge m$.

*Sketch of the proof.* If $D$ has no sources nor sinks, then we are done, so suppose otherwise. In what follows, given a source $s$ in $D$ (resp., a sink $t$), we describe a process that builds a model for an in-arc that we add to $s$ (resp., an out-arc that we add to $t$), so that the obtained supergraph has also a model in a cylindrical grid and has one less source (resp., sink). By iteratively applying such process, we get the desired conclusions.

Let us consider a butterfly model $\eta$ of $D$ with a dijoin path $P^*$ as in Lemma 1, and suppose that $D$ has a source $s$ (the case of a sink is symmetric). We will add a new arc $(z, s)$ for some $z \in V(D)$, and a directed path $Q$ (finishing in the in-tree of the model of $s$) for modelling this arc in the existing model $\eta$. The difficulty is to find the vertex of an out-tree in which we can start $Q$ from. First let us add two columns between any two consecutive columns and let us add two rows between any two consecutive rows. We also add one column to the left and one column to the right of the cylindrical grid.

Let $r_s$ be the root of $\eta(s)$. Note that, by assuming $\eta$ to be minimal, we get that the in-tree of the model of $s$ in $\eta$ is reduced to its root. Let $a_1$ be the vertex below $r_s$ and $b_1$ the vertex below $a_1$. Since we have just added two rows between any two rows, and because the in-tree of $s$ is reduced to $r_s$, we get that $a_1, b_1$ are not part of the model of any vertex nor arc. Let $Q$ initially contain just the arc $(a_1, r_s)$ (this will actually be the last arc of $Q$). Let us assume that $Q$ has been built up to some vertex $a_h$, i.e., $Q = (a_h, a_{h-1}, \cdots, a_1, r_s)$, and additionally assume that the vertex $b_h$ below $a_h$ is not part of the model of any vertex nor arc (this is the case for $h=1$). Let $w$ be the vertex below $b_h$.
- If $w$ is not part of the model of any vertex nor arc, then let $a_{h+1} = b_h$ and let $b_{h+1} = w$, and we continue to build $Q$.

- If $w$ is in the out-tree of some vertex, then add $(w, b_h)$, $(b_h, a_h)$ to the end of $Q$ to be done.

- If $w$ is part of the in-tree of some vertex $a$ (and not of its out-tree, i.e., $w$ is not the root of the model of $a$), then assume that the row of $a_h$ goes to the right (the other case is symmetric). Let $x$ be the left neighbor of $a_h$, $y$ be the vertex below $x$ (and to the left of $b_h$), and $z$ the vertex below $y$ (and to the left of $w$). Note that, since $w$ is part of the model and $b_h$ is not, then the rows of $b_h$ and $a_h$ are rows that have been added just before starting the process. In particular, this implies that either both $x$ and $y$ belong to the model of some $e \in V(D) \cup A(D)$, or neither $x$ nor $y$ is part of any model. We can then prove that the former case is not possible because it would contradict the fact that $w$ is part of the in-tree (and not of the out-tree) of the model of $a$. In the latter case, we set $a_{h+1} = x$ and $b_{h+1} = y$ and go on.

- If $w$ is part of the model of some arc $e = (u, v) \in A(D)$. We apply similar arguments and omit the proof because of space constraints.

The above process is not ensured to finish because if might happen that vertices $a_h$ and $b_h$ are already on the outerface of the model $\eta$. The next two cases allow to ensure that our process will actually terminate. For this purpose, we use the dijoin path $P^*$.

- If $(b_h, a_h)$ crosses the dijoin path $P^*$ and $P^*$ does not cross any blue arc, then let us consider the closest row under $P^*$ that contains a vertex of the model. W.l.o.g., let us assume that this row goes to the right and let $x$ be the rightmost vertex of this row that is part of the model of some vertex $v^*$ of $D$. By minimality of the model and because $x$ has no out-neigbour in the model of any vertex or arc, then, $x$ must be the root of $\eta(v^*)$ (which is actually an in-tree). Now, we add to $\eta(v^*)$: the up-going arc $(x, y)$ ($y$ being the up-neighbor of $x$), and the horizontal directed path $Y$ starting from $y$ to the leftmost vertex of this row (then $y$ becomes the new root of $\eta(v^*)$ and the path $Y$ will be considered as its out-tree). To conclude this case, add at the beginning of $Q$, the directed path from the path $Y$ of $\eta(v^*)$ (added in previous paragraph) to $b_h$.

- If $(b_h, a_h)$ crosses $P^*$ which crosses some blue arc, then we apply similar arguments and omit the proof because of space constraints.

窄

**Further work.** An interesting question is whether there exists a structural condition on the sources and sinks of a digraph $D$ that corresponds to being a butterfly minor of a cylindrical grid (avoiding to invoke a supergraph without sources or sinks). This may help to answer the question of the computational complexity of deciding if a strong digraph $D$ has the EP property when $D$ is not weakly 3-connected. Since the class of digraphs that are butterfly minors of a cylindrical grid is closed under taking butterfly minors, it would also be interesting to characterize the minimal forbidden butterfly minors for this class.
References

1. A. Amiri, K. Kawarabayashi, S. Kreutzer, and P. Wollan. The Erdos-Pósa property for directed graphs. *arXiv preprint arXiv:1603.02504*, 2016.

2. J. Bang-Jensen and G. Gutin. *Digraphs Theory, Algorithms and Applications*. Springer-Verlag, 2 edition, 2008.

3. P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel. Representing a planar graph by vertical lines joining different levels. *Discrete Math.*, 46:319–321, 1983.

4. P. Erdős and L. Pósa. On independent circuits contained in a graph. *Canadian Journal of Mathematics*, 17:347–352, 1965.

5. T. Johnson, N. Robertson, P. Seymour, and R. Thomas. Directed tree-width. *Journal of Combinatorial Theory, Series B*, 82(1):138–154, 2001.

6. B. Reed, N. Robertson, P. Seymour, and R. Thomas. Packing directed circuits. *Combinatorica*, 16(4):535–554, 1996.

7. N. Robertson and P. Seymour. Graph minors v. excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41:92–114, 1986.

8. N. Robertson and P. Seymour. Graph minors. vii. disjoint paths on a surface. *Journal of Combinatorial Theory, Series B*, 45(2):212–254, 1988.

9. R. Tamassia and I.G. Tollis. A unified approach to visibility representations of planar graphs. *Discrete and Computational Geometry*, 1:321–241, 1986.

10. Douglas B. West. *Introduction to Graph Theory*. Prentice Hall, 2 edition, September 2000.

11. H. Whitney. 2-isomorphic graphs. *American Journal of Mathematics*, 55(1):245–254, 1933.

12. D. Younger. Graphs with interlinked directed circuits. In *Proceedings of the Mid-west Symposium on Circuit Theory*, volume 2, 1973.
A Basic results

In this section, we present a number of simple known facts concerning planar
graphs and their duals. The interested reader can find proofs for such facts in
most graph theory books. We refer to [10].

In a digraph, a vertex with no in-neighbors (resp., no out-neighbors) is called
a *source* (resp. a *sink*). A *plane (di)graph* *D* is a planar (di)graph together with
a planar embedding. Given a plane undirected graph *G* = (*V*, *E*), let *G*\* =
(*V*\*, *E*\*) be its *dual*. That is, the dual graph *G*\* of *G* (with a fixed planar
embedding) is the graph that has a vertex in *V*\* for each face of the embedding
of *G* and *G*\* has an edge *e*\* = {*u*, *v*} ∈ *E*\* for each two faces *u* and *v* in the
embedding of *G* that are separated from each other by an edge *e* ∈ *E*. The
edge *e*\* is the *dual edge* of *e*. If a same face appears on both sides of an edge
*e* ∈ *E*, then *e*\* is a self-loop of *G*\*. For a plane digraph *D*, the dual graph *D*\* is
made directed as well, by orienting each dual arc *e*\* by a 90° clockwise turn from
the corresponding primal arc *e*. For instance, if a face of a plane digraph *D* is
"surrounded" by a directed cycle oriented clockwise (resp., counter-clockwise),
then the corresponding vertex of *D*\* is a source (resp., a sink). Note that *D*\* is
also a plane digraph and that (*D*\*)\* is nothing but the digraph obtained from
*D* by reversing all arcs. A digraph *D* = (*V*, *A*) is *strong* if and only if, for every
distinct *u*, *v* ∈ *V*, there exists a directed *u*, *v*-path in *D*. *D* is a *Directed Acyclic
Graph (DAG)* if it is acyclic, i.e., it has no directed cycle.

Recall the folklore fact that, in the context of planar digraphs, being acyclic
and being strong are dual notions.

**Observation 9** A plane digraph *D* is strong if and only if *D*\* is a DAG.

Given a digraph $D = (V, A)$ and $e \in A$, recall that $D \setminus e$ is the digraph $(V, A \setminus \{e\})$, and that $D/e$ is the digraph obtained from $D$ after contracting the arc $e$. The following result is obvious.

**Observation 1** Let $D = (V, A)$ be a plane digraph, and $e \in A$ be any arc of $D$. Then, $(D \setminus e)^* = D^* / e^*$ and $(D/e)^* = D^* \setminus e^*$.

Recall the definitions of dijoin and feedback arc set. The following observation
is well known.

**Observation 10 ([2])** Let $D = (V, A)$ be a plane digraph. A set of arcs $X \subseteq A(D)$ is a dijoin of $D$ if, and only if, $\{e^* \in A(D^*) | e \in X\}$ is a feedback arc set of $D^*$.

Given a digraph *D*, its *decomposition into strongly connected components* is the digraph *D'* having a vertex *v*<sub>*C*</sub> for each *C* of the (maximal) strongly connected components of *D*, and in which two vertices *v*<sub>*C*</sub> and *v*<sub>*C*'</sub> are joined by an arc from *v*<sub>*C*</sub> to *v*<sub>*C*'</sub> if there is an arc from *C* to *C*'<sup>′</sup> in *D*. Note that *D*'<sup>′</sup> is always a DAG. A source (resp., a sink) of *D*'<sup>′</sup> is called a *source component* (resp., a *sink component*). These notions relate to dijoin paths in the following way.
**Observation 2** A digraph $D$ admits a dijoin path if, and only if, the decomposition of $D$ into strongly connected components has a single source component and a single sink component.

*Proof of the claim.* Assume that the decomposition of $D$ into strongly connected components has a single source component $S$ and a single sink component $T$. Let $P$ be any directed path of $D$ from any vertex of $S$ to any vertex of $T$. Let $(X, V \setminus X)$ be any dicut with arc-set $C \subseteq A$. Then, $S \subset X$ and $T \subset V \setminus X$. Therefore, $A(P)$ must intersect $C$, and so $P$ is a dijoin path.

On the other hand, assume that the decomposition of $D$ into strongly connected components has at least two source components $S$ and $S'$ (the case when it has at least two sink components being symmetric). Let $P$ be any directed path in $D$. W.l.o.g., $P$ has no vertex in $S'$. Then $C = (S', V \setminus S')$ is a dicut and $P$ does not intersect its arc-set. Hence, $P$ is not a dijoin path of $D$. ◇

We finish off with a few facts on dijoin paths.

**Observation 3** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $e \in A \setminus A(P)$. Then, $P$ is a dijoin path of $D \setminus e$.

Note that if the arc $e$ that is contracted in the observation below has its two ends in $P$ (but $e$ is not in $P$) then it may imply that $P'$ is not a path anymore (but a walk). This issue is dealt with in the following Observation 6.

**Observation 4** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $e \in A$. Let $P'$ be obtained from $P$ by contracting $e$ if $e \in A(P)$, and $P' = P$ otherwise. Then, $P'$ is a dijoin walk of $D/e$.

**Observation 5** Let $D = (V, A)$ be a digraph with a dijoin path $P$, and $v \in V$ be an isolated vertex. Then, $P$ is a dijoin path of $D \setminus v$.

**Observation 6** Every digraph with a dijoin walk admits a dijoin path.

*Proof of the claim.* Let $P = (v_1, \cdots, v_p)$ be a shortest dijoin walk of $D$ and, for purpose of contradiction, let us assume that $P$ is not a dijoin path. That is, there are $i < j$ such that $v_i = v_j$. Since $(v_i, \cdots, v_j)$ is a directed cycle, for every dicut $(X, V \setminus X)$, either $\{v_i, \cdots, v_j\} \subseteq X$ or $\{v_i, \cdots, v_j\} \subseteq V \setminus X$. Hence, the arc-set of $P' = (v_1, \cdots, v_i, v_{i+1}, \cdots, v_p)$ also intersects the arc-sets of all dicuts. Therefore, $P'$ is a shorter dijoin walk, a contradiction. ◇

Recall that a model of $G$ in $H$ is *minimal* if, for every $v \in V(G)$ and for every leaf $w$ of $\eta(v)$, $w$ is incident to some blue arc. Up to removing the leaves that do not satisfy this property from $\eta(v)$, we get that the following holds:

**Observation 11** If a graph $G$ has a model in some graph $H$, then $G$ has a minimal model in $H$.
## B Formal definition of the adding rows or columns operations

We will deal with butterfly models of a digraph in $C_{n,2m}$ through a few operations. Let $\eta$ be a butterfly model of a digraph $D$ in $C_{n,2m}$. Due to lack of space, we only present them informally.

- Adding $x \ge 1$ columns between columns $i$ and $i+1$ in $\eta$ consists in considering the new model $\eta'$ of $G$ in the cylindrical grid $C_{n+x,2m}$ defined as follows. Intuitively, all the elements of the model to the left of column $i$ (or in column $i$) remain the same, all elements of the model to the right of column $i$ are translated from $x$ columns toward the right and all horizontal arcs from column $i$ to column $i+1$ are replaced by horizontal paths with $x+1$ arcs (from the column $i$ to the column $i+x+1$ in the resulting model). More formally, for every $y \in V(G) \cup A(G)$ and for every $e = ((\ell,j), (\ell',j')) \in \eta(y)$, if $\ell, \ell' \le i$, then $e \in \eta'(y)$, if $\ell, \ell' > i$, then $((\ell+x,j), (\ell'+x,j')) \in \eta'(y)$. Finally, if $\ell = i$ and $\ell' = i+1$ (so $j = j'$), then the arcs $((\ell,j), (\ell+1,j))$, $((\ell+1,j), (\ell+2,j))$, \dots, $((\ell+x,j), (\ell+x+1,j))$ are added to $\eta'(y)$. Symmetrically, if $\ell = i+1$ and $\ell' = i$ (so $j = j'$), then the arcs $((\ell+2x+1,j), (\ell+2x,j))$, $((2x,j), (2x-1,j))$, \dots, $((\ell+1,j), (\ell,j))$ are added to $\eta'(y)$. Note that no vertical arcs of the $x$ added columns belong to the new model $\eta'$ of $D$. See Figure 4 for an illustration.

- Adding $2x \ge 2$ rows between rows $j$ and $j+1$ in $\eta$ consists in considering the new model $\eta'$ of $G$ in the cylindrical grid $C_{n,2(m+x)}$ defined as follows. For every $y \in V(G) \cup A(G)$ and for every $e = ((i,\ell),(i',\ell')) \in \eta(y)$, if $\ell, \ell' \le j$, then $e \in \eta'(y)$, if $\ell, \ell' > j$, then $((i,\ell+2x),(i',\ell'+2x)) \in \eta'(y)$. Finally, if $\ell = j$ and $\ell' = j+1$ (so $i = i'$), then the arcs $((i,\ell),(i,\ell+1)), ((i,\ell+1),(i,\ell+2)), \dots, ((i,\ell+2x),(i,\ell+2x+1))$ are added to $\eta'(y)$. Note that no horizontal arcs of the $2x$ added rows belong to the new model $\eta'$ of $D$. See Figure 4 for an illustration.

## C Omitted proofs from Section 3

**Theorem 4.** Let $D = (V, A)$ be a digraph without sources or sinks. If $D$ has a planar embedding such that $D^*$ admits a dijoin path $P^*$, then $D$ has a butterfly model in $C_{n,2m}$ for some $n, m \in \mathbb{N}^*$.

*Proof.* By Observation 8, $D_{P^*}(s,t)$ is a DAG with a unique source $s$, a unique sink $t$, and $(s,t) \in A(D_{P^*}(s,t))$. By Theorem 3, there exists an increasing visibility representation of $D_{P^*}(s,t)$. Let $V(D_{P^*}(s,t)) = \{s = v_1, \dots, t = v_n\}$ be ordered increasingly according to their $y$-coordinates on the representation and suppose, without loss of generality, that the $y$-coordinate of $h_{v_1}h_s$ is 0 and the difference between the $y$-coordinates of $h_{v_i}$ and $h_{v_{i-1}}$ is 2 (their value on the constructed increasing visibility representation are all different, so we just need to adjust it). Observe that, in this case, the $y$-coordinate of $h_{v_i}$ is $2i-2$. We will build a model of $D$ in some cylindrical grid as follows.
For each $v_i \in V(D)$ (hence $i \notin \{1, n\}$), let $h'_{v_i}$ be the segment equivalent to $h_{v_i}$, but in the upper row. In other words, $h'_{v_i}$ has $y$-coordinate $2i-1$, and leftmost and rightmost $x$-coordinates equal to the ones of $h_{v_i}$. The idea of the proof is to relate $v_i$ with the path formed by the union of paths associated to $h'_{v_i}$ and $h_{v_i}$ in the cylindrical grid (see Figure 6). Since all arcs of $D$ are “pointing upwards”, we get that the subpath associated to $h'_{v_i}$ (i.e., in row $2i-1$) corresponds to the out-tree of $v_i$, while the subpath associated to $h_{v_i}$ (i.e., in row $2i-2$) corresponds to the in-tree of $v_i$. We formalize this proof in what follows.

Because $D_{P^*}(s, t)$ is finite, we can suppose that the coordinates of the end-points of the segments $(\{h_u\}_{u \in V(D_{P^*}(s,t))}, \{t_e\}_{e \in A(D_{P^*}(s,t))})$ are all integers. Let $k \in \mathbb{N}$ be equal to the maximum $x$-coordinate of some arc. We first construct a butterfly model $\eta$ of $D_{P^*}(s, t)$ into the cylindrical grid $C_{k,2n}$ as follows.

For every $1 \le i \le n$, let $(j, 2i-2)$ and $(\ell, 2i-2)$ be the coordinates of the leftmost and rightmost points of $h_{v_i}$ respectively ($j \le \ell$). Let $P_i$ be the subpath of the cylindrical grid whose first vertex is $(j, 2i-2)$ and last vertex is $(\ell, 2i-2)$. Note that $2i-2$ being even, the corresponding row goes to the right. Let $Q_i$ be the path whose first vertex is $(\ell, 2i-1)$ and last vertex is $(j, 2i-1)$ (the corresponding row goes to the left). Let us define $\eta(s) = \eta(v_1) = Q_1$, $\eta(t) = \eta(v_n) = Q_n$ and, for every $1 < i < n$, let $\eta(v_i) = P_i \cup ((\ell, 2i-2), (\ell, 2i-1)) \cup Q_i$. For $1 < i < n$, we can consider $\eta(v_i)$ as an in-out-branching with root $(\ell, 2i-2)$. Observe that, for every $v_i \ne v_j$, since $h_{v_i}$ and $h_{v_j}$ have different $y$-coordinates, and the difference between the $y$-coordinates of $h_{v_i}$ and $h_{v_{i-1}}$ is 2, $\eta(v_i)$ and $\eta(v_j)$ are vertex-disjoint.

For the vertical segments $\{t_e\}_{e \in A(D_{P^*}(s,t))}$, that represent the arcs of $D_{P^*}(s,t)$, if $t_{v_iv_j}$ is a segment with endpoints in $h_{v_i}$ and $h_{v_j}$ with $x$-coordinate $m$, for $i < j$, we make $\eta(v_iv_j) = ((m, 2i-1), (m, 2i), (m, 2i+1), \dots, (m, 2j-2))$, where $(m, 2i-1) \in Q_i$ and $(m, 2j-2) \in P_j$. So, $\eta(v_iv_j)$ is a path from the out-branching of $\eta(v_i)$ to the in-branching of $\eta(v_j)$. Since the vertical segments are non-overlapping and by the way we model the vertices of $D_{P^*}(s,t)$ through the visibility representation, $\eta(e)$ and $\eta(e')$ are vertex-disjoint, for every distinct $e, e' \in A(D_{P^*}(s,t))$.

Now, we want to use $\eta$ to construct a butterfly model $\nu$ of $D$ in some cylindrical grid $C_{k,2l}$ (initially, $l=n$ but it might increase during the process below). Start by letting $\nu(u) = \eta(u)$, for every $u \in V(D)$ (i.e., we ignore vertices $s$ and $t$), and let $N_{D_{P^*}(s,t)}^{+}(s) \setminus \{t\} = \{w_1, \dots, w_p\}$, and $N_{D_{P^*}(s,t)}^{-}(t) \setminus \{s\} = \{u_1, \dots, u_p\}$. Observe that, for each $m \in \{1, \dots, p\}$, there is a path $\eta(u_m, t) = ((j_m, i), (j_m, i+1), \dots, (j_m, 2n-2))$ that models arc $(u_m, t)$ (note that $i=2j-1$ where $j$ is the index such that $u_m = v_j$). The value $j_m$ is called the $x$-coordinate of $u_m$. Similarly, there is a path $\eta(s, w_m) = ((\ell_m, 1), (\ell_m, 2), \dots, (\ell_m, i'))$ that models arc $(s, w_m)$ (where $i'=2j'-2$ where $j'$ is the index such that $w_m = v_{j'}$), and let $\ell_m$ be the $x$-coordinate of $w_m$, for each $m \in \{1, \dots, p\}$.

Note that, the arcs in $\{(u_i, w_i) | 1 \le i \le p\}$ are exactly the arcs of $D$ that are not modeled in $\eta$. Recall that these arcs are ordered according to the path $P^*$ (see Figure 5). We start with $\nu(u_i, w_i) = \eta(u_i, t) \cup \eta(s, w_i)$. Note that $(j_i, 2n-2)$ (resp., $(\ell_i, 1)$) are the coordinates of the topmost (resp., bottommost) endpoint
<figure><img src="image_7.png" /><figcaption>Fig. 6: Constructing a model from a visibility representation of a DAG.</figcaption></figure>

of $\eta(u_i t)$ (resp., of $\eta(sw_i)$). Let us add $2n$ rows between the row $2n-2$ and the row 1. Since $j_1 \le \dots \le j_p$ and $\ell_1 \le \dots \le \ell_p$, there are $p$ vertex-disjoint directed paths $(H_i)_{1 \le i \le p}$ from $(j_i, 2n-2)$ to $(\ell_i, 1)$ respectively, using the $2n$ new rows. For every $1 \le i \le p$, add $H_i$ to $\nu(u_i, w_i)$. $\square$

## D Omitted proofs from Section 4

**Observation 12** Let $D = (V, A)$ be a digraph. If $D$ has a butterfly model in $C_{n,2m}$, then $D$ has a butterfly model in $C_{n',2m'}$ for some $n' \ge n$ and $m' \ge m$ such that every blue arc with tail a black vertex is vertical.

*Proof.* Consider any blue arc $(u, v) \in A(C_{n,2m})$ of the model $\eta$ of $D$ such that its tail is black. Note that it means that $u$ is a vertex of the out-tree of $\eta(w^*)$ for some $w^* \in V(D)$ and that there exists an arc $a^* = (w^*, x) \in A(D)$ such that $(u, v) \in A(\eta(a^*))$. Let $(i, j)$ be the coordinates of $u$ in $C_{n,2m}$.

Let us assume that $(u, v)$ is horizontal to the right (i.e., $v$ has coordinates $(i+1, j)$). The case when $(u, v)$ is horizontal to the left is symmetric. Let us describe a transformation (which is depicted in Figure 7) that will give a new model $\nu$ where this blue arc has been “turned up” (i.e., it becomes a vertical arc).

First add one column between columns $i$ and $i+1$. The new column is then index $i+1$. Intuitively, we move up the part to the left of the new column $i+1$ (included) from row $j+1$, then we move up the part to the right of column $i+1$ from row $j$. In other words, we subdivide twice all edges between row $j$ and $j+1$.
<figure><img src="image_8.png" /><figcaption>Fig. 7: Illustration of operation performed on arc $(u, v)$ in the proof of Observation 12. Rows and column highlighted in green are the “added” rows and column. The red lines emphasize the last modifications.</figcaption></figure>

that are to the left of column $i+1$, and all edges between row $j-1$ and $j$ that are to the right of column $i+1$. The only possible interaction between left and right (and up and down) that is not naturally within an embedding in a bigger cylindrical grid is the one between columns $i$ and $i+1$ in row $j$. This is considered in a last step by increasing the out-tree of $w^*$ with the arc $((i,j), (i+1,j))$, while removing the same arc from $\eta(a^*)$ and adding arcs $((i+1,j), (i+1,j+1))$ and $((i+1,j+1), (i+1,j+2))$ to $\eta(a^*)$. The formal arguments are presented below.

Now, let us formally define the above transformation. First, a new column is added between columns $i$ and $i+1$, according to the transformation defined in the preliminaries section. The new column has now abscissa $i+1$ and recall that no vertical arc of this column belongs to the model of any vertex or arc of $D$.

Let $B$ be the set of vertices $(x, y)$ of the grid such that either $y < j$, or $y = j$ and $x < i + 1$, and let $T$ be the remaining vertices (i.e., $(B, T)$ is a partition of the vertices of the cylindrical grid). Note that the only arcs of the model of $D$ that go from one part to the other are: the arc $((i, j), (i+1, j))$ (that results from the subdivision of $(u, v)$ when the new column has been added); the vertical arcs of the form $((\ell, j)(\ell, j+1))$ with $\ell \le i$ or $((\ell, j-1)(\ell, j))$ with $\ell > i$; and the
vertical arcs between the topmost row and the bottommost row, i.e., of the form
((ℓ, 2m − 1), (ℓ, 0)). The new model η' is defined as follows:

- for every arc (a, b) of the model of $e \in V(D) \cup A(D)$, i.e., $(a, b) \in A(\eta(e))$,
such that a and b belong to B, then $(a, b) \in A(\eta'(e))$;

- for every arc ((ℓ, h), (ℓ', h')) of the model of $e \in V(D) \cup A(D)$, i.e., ((ℓ, h), (ℓ', h')) ∈ A(η(e)), such that (ℓ, h) and (ℓ', h') belong to T, then ((ℓ, h+2), (ℓ', h'+2)) ∈ A(η'(e));

- for every arc ((ℓ, 2m − 1), (ℓ, 0)) of the model of $e \in V(D) \cup A(D)$, i.e.,
  ((ℓ, 2m − 1), (ℓ, 0)) ∈ A(η(e)), then ((ℓ, 2m + 1), (ℓ, 0)) ∈ A(η'(e));

- for every arc ((ℓ, j)(ℓ, j + 1)) with ℓ ≤ i such that ((ℓ, j)(ℓ, j + 1)) ∈ A(η(e)) for some e ∈ V(D) ∪ A(D), then ((ℓ, j)(ℓ, j + 1)), ((ℓ, j + 1)(ℓ, j + 2)) and ((ℓ, j + 2)(ℓ, j + 3)) are added to η'(e);

- for every arc ((ℓ, j - 1)(ℓ, j)) with ℓ > i such that ((ℓ, j - 1)(ℓ, j)) ∈ A(η(e))
  for some e ∈ V(D) ∪ A(D), then ((ℓ, j - 1)(ℓ, j)), ((ℓ, j)(ℓ, j + 1)) and ((ℓ, j + 1)(ℓ, j + 2)) are added to η'(e);

- Finally, the arc ((i, j), (i + 1, j)) is added to η'(w*) (recall that w* ∈ V(D) is the vertex whose u is part of the out-tree) and the arcs ((i + 1, j)(i + 1, j + 1)) and ((i + 1, j + 1)(i + 1, j + 2)) are added to η(a*) (recall that (u, v) was part of the model of a* ∈ A(D)).

Let us show that $\eta'$ is a valid model of $D$. Indeed, consider any path $P$ in $\eta$. If all vertices of $P$ belong to $B$, then $P$ is invariant by the transformation. If all vertices of $P$ belong to $T$, then the image of $P$ in $\eta'$ is the same path moved up by two rows (in particular, the orientations of the horizontal arcs remain consistent). Or $P = P' \odot a \odot Q'$ (where $\odot$ denotes the concatenation) with $P'$ is a path with all its vertices in $B$, $Q'$ is a path with all vertices in $T$ and the arc $a$ is (1) either $(u, v)$, or (2) an arc (($(\ell, j)(\ell, j + 1)$) with $\ell \le i$ or (3) an arc (($(\ell, j - 1)(\ell, j)$) with $\ell > i$. In all cases, $P'$ remains invariant and $Q'$ is translated up by two rows. In cases (2) and (3), the image of $a$ by $\eta'$ is a path of length 3 that connects the last vertex of the image of $P'$ to the first vertex of the image of $Q'$. In the case (1), the image of $a$ is the path with arcs (($(i, j), (i + 1, j)$), (($(i + 1, j)(i + 1, j + 1)$) and (($(i + 1, j + 1)(i + 1, j + 2)$) which again leads to a valid path.

To conclude, the image of $a^*$ by $\eta'$ now starts by a vertical blue arc (the arc $((i+1,j)(i+1,j+1))$).

Repeating iteratively this process (to all horizontal blue arc with a black vertex as tail) eventually ensures a model that satisfies the statement. $\square$

**Lemma 1.** If a digraph *D* has a butterfly model η in C<sub>*n*,2*m*</sub>, then *D* has a butterfly model in C<sub>*n*',2*m*'</sub> for some *n*' ≥ *n* and *m*' ≥ *m* such that no black arcs of this model are dual of an arc of Q<sub>*n*',2*m*'</sub>^*.

*Proof.* If $Q_{n,2m}^*$ does not “cross” any black arc in the given model $\eta$, then we are done. Otherwise, let $k$ be the number of black arcs crossed by $Q_{n,2m}^*$ and let $(x, y)$ be the leftmost black arc which is the dual of an arc of $Q_{n,2m}^*$. Let $v \in V(D)$ such that $(x, y) \in \eta(v)$. Let us assume that $(x, y)$ belongs to the
out-tree of $\eta(v)$ (the case when it is in the in-tree is symmetric). Let $T_v$ be the subtree of the out-tree of $\eta(v)$ induced by $(x, y)$ and all vertices of $\eta(v)$ that can be reached from $y$ in $\eta(v)$. Let $k'$ be the number of blue arcs with tail in $T_v$. We present a process such that either we strictly decrease $k$ (in the case $k' = 1$), or $k$ remains the same but $k'$ decreases. Therefore, eventually (when $k = 0$), we obtain the desired model. Throughout the proof, we use $n', m'$ to denote the dimensions of the current model/path.

- Let us assume that $k' = 1$. Hence, since we may assume that the model is minimal (by Observation 11), then $T_v$ is a directed path $P$. Let $e'$ be the blue arc with tail in $T_v$. We have $e' \in \eta(e)$ for some arc $e = (v, w) \in A(D)$. Intuitively, we remove $P \cup \{(x, y)\}$ from the model of $w$ and add it to the model of $e$. More formally, let $H = \eta(e)$ be the directed blue path modeling $e$. We define the new model $\eta'$ of $G$ in $C_{n',2m'}$ as follows: for every $z \in E(G) \cup V(G) \setminus \{v,w,e\}$, $\eta'(z) = \eta(z)$. Then, $\eta'(v) = \eta(v) \setminus (P \cup \{(x,y)\})$, $\eta'(w) = \eta(w)$ and $\eta'(e) = \{(x,y)\} \cup (P \cup H)$. Since $(x,y)$ is now a blue arc (and no blue arc has been changed to black), we decreased by one the number of black arcs crossed by $Q_{n,2m'}^*$.

- Now, let us consider the case when $k' > 1$. We first need some technical modifications of the model.

* First, we would like to ensure that $x$ is on a row going to the right. If $x$ is on a row going to the left, let $j$ be the row of $x$. We add two rows $a$ and $b$ between rows $j$ and $j-1$, where $a$ is the row going to the right. We replace $Q_{n',2m'}^*$ (which was between rows $j$ and $j+1$) by the parallel dijoin path between the new rows $j$ and $a$. This new path still intersects the same number of black arcs and the only difference is that it intersects $T_v$ in the arc $(x', y')$ (where $y' = x$) and $x'$ is on a row going to the right. Hence, going back to the initial notation, we may assume that $x$ is on a row going to the right.

* Then, we would like that $x$ is not the head of a black or blue vertical arc. If this is the case, let us apply an operation that ensures that $x$ is not the head of a black or blue vertical arc, and that its left neighbor is also part of the out-tree of $v$. Let $(i, j)$ be the coordinates of $x$. First, add one column to the right of $x$ (i.e., between columns $i$ and $i+1$). Then, remove $(x, y) = ((i, j), (i, j+1))$ from $\eta(v)$ and add $((i+1, j), (i+1, j+1))$ to $\eta(v)$ (this will be our "new" arc crossing $Q_{n,2m'}^*$, i.e., replacing $(x, y)$), add $((i, j), (i+1, j))$ to $\eta(v)$ (if it was not already part of it) and finally, add $((i+1, j+1), (i, j+1))$ to $\eta(v)$ (note that this last arc was not part of any model because $y$ is in the out-tree of $\eta(v)$ and had $x$ has unique in-neighbor). Now, the vertices $(i+1, j)$ and $(i+1, j+1)$ play the role of $x$ and $y$ respectively. Hence, we may assume that $x$ is not the head of a black or blue vertical arc and that its left neighbor is also part of the out-tree of $v$, as we wanted to show.

Now, we are ready for the main work. The technical process defined below is depicted in Figure 8.

Start a DFS of $T_v$ from the arc $(x, y)$ with the following priorities: if possible, go to the left, else if it is possible go up, and go to the right otherwise. Stop
<figure><img src="image_9.png" /><figcaption>Fig. 8: Construction of $P'$ (visualized by the red line in (b)) from $P$ (drawn in red in (a)). In (b), lines and columns highlighted in green are added lines and columns.</figcaption></figure>

as soon as you reach a leaf $z$ of $T_v$. By minimality of the model, $z$ must be the tail of a blue arc $e = (z, z')$. Note that by Observation 12, we may assume that $(z, z')$ is a vertical arc. Let $P$ be the subpath of $T_v$ from $x$ to $z$. Let $f \in A(D)$ such that $e \in \eta(f)$.

We will increase the cylindrical grid to make “some space”. For every column $i$ such that $P$ has at least one vertical arc in column $i$, add one column between column $i-1$ and column $i$. In particular, we add one column to the left of $x$. For every row $j$ such that $P$ has at least one arc going right in row $j$, add two rows between rows $j$ and $j+1$. Finally, for every row $j$ such that $P$ has at least one arc going left in row $j$, add two rows between rows $j-1$ and $j$. Note that these additions of rows and columns do not change the main properties of the model of $D$ in the new larger grid $C_{n',2m'}$ (abusing the notation we still denote this model by $\eta$): blue arcs with head in an in-tree are vertical, models of vertices are still minimal and, more important, $Q_{n',2m'}^*$ still crosses $k$ black arcs and there are $k'$ blue arcs with tail in $T_v$. We now modify the model $\eta$ into a new one $\eta'$ that differs only on $v$ and $e$. Start with $\eta'(q) = \eta(q)$ for all $q \in V(D) \cup A(D)$. Now, let $x'$ be the left neighbor of $x$. It exists since we have added a column to the left of $(x, y)$ and $x'$ is part of the out-tree of $v$ by the initial technical modifications. Observe also that $x'$ is the only in-neighbor of $x$ in $T_v$. Intuitively, we will
now add to $\eta'(v)$ a path $P'$ that starts in $x'$ and is "parallel" to $P$ using
the added rows and columns. In what follows, we describe the path $P$ as
its sequence of arcs starting from $(x, y)$. In addition to the starting arc, we
only need the sequence of orientations: going up (U), right (R) or left (L), of
each arc to well describe $P$. Hence, let $P = (\alpha_0 = (x, y), \alpha_1, \dots, \alpha_p)$ where
$\alpha_i \in \{U, R, L\}$ for every $1 \le i \le p$. We build $P'$ iteratively starting from the
up-going arc $(x', y')$ where $y'$ is the up neighbor of $x'$. Note that, because
of the added rows and columns, $y'$ cannot be in the model of any element
of $D$. Assume that $P' = (\beta_0 = (x', y'), \beta_1, \dots, \beta_{q'})$ has already been built
and corresponds to the prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_q)$ of $P$ (it holds for
$q = q' = 0$). We extend $P'$ depending on the next one, two or three arcs of
$P$.

* If $(\alpha_{q+1}, \alpha_{q+2}, \alpha_{q+3}) = (UUL)$, add nothing to $P'$. Then, $P'$ corresponds to the new prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_{q+3})$ of $P$;

* If $(\alpha_{q+1}, \alpha_{q+2}, \alpha_{q+3}) = (RUU)$, add nothing to $P'$. Then, $P'$ corresponds to the new prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_{q+3})$ of $P$;

* If $(\alpha_{q+1}, \alpha_{q+2}) = (UR)$, add $(UUURR)$ to $P'$. Then, $P'$ corresponds to the new prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_{q+2})$ of $P$;

* If $(\alpha_{q+1}, \alpha_{q+2}) = (LU)$, add $(LLUUU)$ to $P'$. Then, $P'$ corresponds to the new prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_{q+2})$ of $P$;

* Otherwise, add $\alpha_{q+1}$ to $P'$. Then, $P'$ corresponds to the new prefix $P_{pref} = ((x, y), \alpha_1, \dots, \alpha_{q+1})$ of $P$;

Finally, we explain how to deal with $\eta(f)$. Recall that $z$ was the last vertex of $P$, that it was the tail of a vertical blue arc $(z, z')$ belonging to the model of the arc $f$. Abusing the notation, we keep the same notation (for $z$ and $z'$) after all transformations above. Hence, let $(i, j)$ be the coordinates of the last vertex $z$ of $P$ (after modifications). There are different cases depending on the orientation of the last arc of $P$.

* If the last arc of $P$ was vertical, then the last vertex of $P'$ has coordinates $(i-1, j)$. First, we remove $(z, z')$ from $\eta'(f)$, and analyse the following cases.

* Row $j+1$ goes to the right. If $z' = (i, j+1)$ is part of the in-tree of some vertex $w \in V(D)$, then add $((i-1, j+1), (i, j+1))$ to $\eta(w)$ and let $\eta'(f) = ((i-1, j), (i-1, j+1))$. Otherwise (hence, $z'$ had degree two in $\eta(f)$), then add $((i-1, j+1), (i, j+1))$ and $((i-1, j), (i-1, j+1))$ to $\eta'(f)$.

* Row $j+1$ goes to the left. First add two new rows between rows $j$ and $j+1$, and write the subpath associated to the subdivision of $(z, z')$ as $(z, t, z''', z')$. If $z'$ is part of the in-tree of some $w \in V(D)$, then add the path $(z'', z''', z')$ to $\eta'(w)$ where $z'''$ is the vertex below $z'$ and $z''$ is the vertex to the left of $z''$, and set $\eta'(f)$ to be equal to the 2-arc path from the end of $P'$ to $z'$. Otherwise, add the path from the endpoint of $P'$ to $z'', z'''$ and $z'$ to $\eta'(f)$.

* If the last arc of $P$ was to the left, then the last vertex of $P'$ has coordinates $(i, j-2)$. First, remove $(z, z')$ from $\eta'(f)$, and add a new column between columns $i$ and $i-1$. If $z' = (i, j+1)$ is part of the in-tree of
some vertex $w \in V(D)$, then add $(z'', z')$ to $\eta'(w)$ where $z''$ is the left neighbor of $z'$ and let $\eta'(f)$ be equal to the 4-arc path from the end of $P'$ to $z''$. Otherwise (hence, $z'$ had degree two in $\eta(f)$), add the 4-arc path from the end of $P'$ to $z''$ and $(z'', z')$ to $\eta'(f)$.

• If the last arc of $P$ was to the right, then the last vertex of $P'$ has coordinates $(i, j + 2)$. Remove the vertical 2-arc path from the end of $P$ to the end of $P'$ from $\eta'(f)$.

Note that, right now, $Q_{n',2m'}^*$ crosses one more black arc (the first one of $P'$). However, since $P'$ is a path, we may proceed as in the first item to “replace” this black arc by a blue one. Therefore, we reach a new model where $Q_{n',2m'}^*$ still crosses $k$ black arcs, the leftmost one being part of the out-tree of $v$ and such that the new $T_v$ has only $k' - 1$ blue arcs with tail in it. $\square$

**Lemma 2.** If a digraph $D = (V, A)$ has a butterfly model in $C_{n,2m}$, then $D$ has a spanning supergraph with neither sources nor sinks that has a butterfly model in $C_{n',2m'}$ for some $n' \ge n$ and $m' \ge m$.

*Proof.* If $D$ has no sources nor sinks, we are done, so suppose otherwise. In what follows, given a source $s$ in $D$ (resp., a sink $t$), we describe a process that builds a model for an in-arc that we add to $s$ (resp., an out-arc that we add to $t$), so that the obtained supergraph has also a model in a cylindrical grid and has one less source (resp., sink). By iteratively applying such process, we finish our proof.

Let us consider a butterfly model $\eta$ of $D$ with a dijoin path $P^*$ as in Lemma 1, and suppose that $D$ has a source $s$ (the case of a sink is symmetric). We will add a new arc $(z, s)$ for some $z \in V(D)$, and a path $Q$ (finishing in the in-tree of the model of $s$) for modelling this arc in the existing model $\eta$. The difficulty is to find the vertex of an out-tree in which we can start our path $Q$. First let us add two columns between any two consecutive columns and let us add two rows between any two consecutive rows. We also add one column to the left and one column to the right of the cylindrical grid. The following process is illustrated in Figure 9.

Let $r_s$ be the root of $\eta(s)$. Note that, by assuming $\eta$ to be minimal (recall Observation 11), we get that the in-tree of the model of $s$ in $\eta$ is reduced to its root. Let $a_1$ be the vertex below $r_s$ and $b_1$ the vertex below $a_1$. Since we have just added two rows between any two rows, and because the in-tree of $s$ is reduced to $r_s$, we get that $a_1, b_1$ are not part of the model of any vertex nor arc. Let $Q$ initially contain just the arc $(a_1, r_s)$ (this will actually be the last arc of $Q$). Let us assume that $Q$ has been built up to some vertex $a_h$, i.e., $Q = (a_h, a_{h-1}, \cdots, a_1, r_s)$, and additionally assume that the vertex $b_h$ below $a_h$ is not part of the model of any vertex nor arc (this is the case for $h = 1$). Let $w$ be the vertex below $b_h$.

- If $w$ is not part of the model of any vertex nor arc, then let $a_{h+1} = b_h$ and let $b_{h+1} = w$, and we continue to build $Q$; For instance, this is the case in Figure 9 when building the path $Q$ between vertices $B$ and $C$;

- If $w$ is in the out-tree of some vertex, add $(w, b_h), (b_h, a_h)$ at the end of $Q$ and we are done.
- If $w$ is part of the in-tree of some vertex $a$ (and not of its out-tree, i.e., $w$ is not the root of the model of $a$), then assume that the row of $a_h$ goes to the right (the other case is symmetric). Let $x$ be the left neighbor of $a_h$, $y$ be the vertex below $x$ (and to the left of $b_h$) and $z$ the vertex below $y$ (and to the left of $w$). Note that, since $w$ is part of the model $b_h$ is not, then the rows of $b_h$ and $a_h$ are rows that have been added just before starting the process. In particular, this implies that, either both $x$ and $y$ belong to the model of some $e \in V(D) \cup A(D)$, or neither $x$ nor $y$ is part of any model. In the latter case, we set $a_{h+1} = x$ and $b_{h+1} = y$ and go on (for instance, this is the case in Figure 9 when building the path $Q$ between vertices $A$ and $B$). Otherwise, we consider the cases:

* $x, y$ are part of the model of a vertex of $D$. Observe that this implies that the column of $x$ and $y$ cannot be one of the added columns, as such columns cannot have arcs inside any model. Moreover, it implies that $w$ belongs to an added column and so is part of the model of the same vertex as its left neighbor $z$. Overall, this implies that all $x, y, z, w$ must be part of the model of the same vertex, say $a$. Recall that the row of $a_h$ goes to the right to see that $z$ has out-degree at least 2 in the model of the vertex $a$. Hence $z$ is in the out-tree of $a$. This is a contradiction as $w$ is in the in-tree of $a$, and there cannot be arcs going from the out-tree to the in-tree of any vertex.

* $x, y$ are part of the model of an arc of $D$. In that case, $z$ must be part of the model of the same vertex $a$ as $w$ (because $w$ is part of the model of a vertex and because of the columns added initially). Because $x$ and $y$ belong to added rows, this implies that the arcs $(x, y)$ and $(z, y)$ have the same status, i.e., they are blue arcs. This implies that $z$ is part of the out-tree of $a$ and so $w$ also, a contradiction.

- If $w$ is part of the model of some arc $e = (u, v) \in A(D)$. Let $M$ be the subpath of $\eta(e)$ until $w$. Let us build a path $M'$ "parallel" to $M$ as we built a path $P'$ parallel to $P$ in the proof of Lemma 1. The first end of $M'$ is a vertex of the out-tree of $u$ and its last end $w'$ is some neighbor of $w$. Finally, we add $Q'$, the path from $w'$ to $a_h$ to $Q$.

The last two cases allow to ensure that our process will actually terminate.
For this purpose, we use the dijoin path $P^*$.

- If $(b_h, a_h)$ crosses the dijoin path $P^*$ and $P^*$ does not cross any blue arc. In this case, let us consider the closest row under $P^*$ that contains a vertex of the model. W.l.o.g., let us assume that this row goes to the right and let $x$ be the rightmost vertex of this row that is part of the model of some vertex $v^*$ of $D$. By minimality of the model and because $x$ has no out-neigbour in the model of any vertex or arc, then, $x$ must be the root of $\eta(v^*)$ (which is actually an in-tree). Now, we add to $\eta(v^*)$: the up-going arc $(x, y)$ ($y$ being the up-neighbor of $x$) and the horizontal path $Y$ starting from $y$ to the leftmost vertex of this row (then $y$ becomes the new root of $\eta(v^*)$ and the path $Y$ will be considered as its out-tree).
<figure><img src="image_10.png" /><figcaption>Fig. 9: Illustration of the process in the proof of Lemma 2.</figcaption></figure>

To conclude this case, add at the beginning of $Q$, the directed path from the path $Y$ of $\eta(v^*)$ (added in previous paragraph) to $b_h$. Then, we are done.

- If $(b_h, a_h)$ crosses $P^*$ which crosses some blue arc. Let $e$ be such a blue arc closest to $a_h$ and let $a = (\alpha, \beta) \in A(D)$ such that $e \in \eta(a)$. Let us assume that $e$ is to the right of $a_h$ (the other case is symmetric). Add at the beginning of $Q$ a path from a left neighbor of $e$ to $a_h$ (it might be needed to add to new rows to get the good orientation). For instance, this is the case in Figure 9 when building the path $Q$ between vertices $D$ and $C$. Hence, our path $Q$ now starts from a left neighbor $\gamma$ of a vertex of $e$. As in the fourth item of this proof, let $M$ be the subpath of $\eta(a)$ which starts from a vertex of the out-tree of $\alpha \in V(D)$ until $e$. Up to adding new rows and new columns, it is possible to add at the beginning of $Q$ a path, “parallel” to $M$, from a vertex of the out-tree of $\alpha$ to $\gamma$. $\square$