Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width

In contrast to and complementing ˜2.1 we propose the following, which was already conjectured by Johnson [12].

It should be noted that in his dissertation, Johnson [12] already discovered the strong structural similarities between Eulerian digraphs and undirected graphs. In fact, he proved a structure theorem for internally $6$-connected $4$-regular Eulerian digraphs, and mentions that he anticipated using it towards proving a well-quasi-order result for Eulerian digraphs by immersion⁸⁸8His definition differs slightly from the standard definition. in the future. Unfortunately, to the best of our knowledge, he never published such results. Nevertheless, this shows that there has been a hunch that Eulerian digraphs may be a particularly interesting candidate for a directed graph class with tamable structural behavior.

Note further that, in contrast to the discussion about the results in [20, 23], if ˜3.1 were true, then the obstructions to well-quasi-ordering Eulerian digraphs by strong immersion are not long alternating paths, but rather vertices of arbitrarily large degree.

Let us discuss a few immediate consequences and important applications that would follow from a proof of ˜3.1.

Note that in the above discussion, we had to restrict to classes of Eulerian digraphs of bounded degree. Unfortunately, ˜2.1 shows that there is no hope to extend ˜3.1 to the class of all Eulerian digraphs. However, we believe that this is an artifact of the strong immersion relation. As the construction in ˜2.1 shows, immersion forces us to map the high degree vertices to each other, and thus they become unusable for routing other paths when dealing with strong immersion. For weak immersion, this is not the case and the high degree vertex in the target digraph can still be used to route further paths. We believe that this is not just an artifact of our construction, but a fundamental difference; we conjecture the following.

This marks a crucial distinction to undirected graphs: If the strong Nash-Williams Conjecture is true (which is commonly believed in the area), then undirected graphs are well-quasi-ordered by strong immersion, whereas Eulerian digraphs are not, but a proof of ˜3.2 would imply that both are well-quasi-ordered by weak immersion. We want to emphasise that a proof of ˜3.2 would immediately lift the above applications regarding Membership Testing to weak immersion and the class of all Eulerian digraphs. That is, any property closed under weak immersion could be tested in polynomial time on the class of Eulerian digraphs.

It may be fruitful to explore whether the above Conjectures 3.1 and 3.2 have implications for other subclasses of directed graphs via suited reductions or decompositions; we leave this for future research.

First, we introduce the concept of $\mathrm{\Omega }$-knitwork, a data structure tailored towards strong immersion of (Eulerian directed) graphs, which seems well suited for proving ˜3.1. In the following exposition, we have simplified the presentation somewhat and tried to focus on the main ideas and concepts. In particular, in several of the following definitions, e.g. in the definition of rooted Eulerian digraphs and of $\mathrm{\Omega }$-knitworks, we left out some extra requirements which are required for the proofs to work but which would only clutter this short version with technical details that we do not have space to explain properly. The full and correct, definitions and results can be found in the full version of this paper [3].

Before going into details, we motivate the concept of $\mathrm{\Omega }$-knitworks by the following example. Suppose we have two Eulerian digraphs $H$ and $G$ and want to immerse $H$ into $G$. Suppose further that there is a set of edges $F_H\subseteq E(H)$ such that deleting $F_H$ from $H$ splits it into disjoint subgraphs $H_1$ and $H_2$; we call $F_H$ a cut. Similarly, assume that there is a cut $F_G\subseteq E(G)$ splitting $G$ into disjoint subgraphs $G_1$ and $G_2$. Now we could try to immerse $H_1$ into $G_1$ and $H_2$ into $G_2$ and from this obtain an immersion of $H$ into $G$ by somehow merging the two immersions of $H_1$ and $H_2$ into $G_1$ and $G_2$, respectively, along the edges in the cut $F_G$. If possible, this would allow for inductive proofs along cuts.

But surely simply recursing into the smaller subgraphs $H_1,H_2,G_1$, and $G_2$ will not be enough. For instance, $H_1$ may no longer be Eulerian as we removed the edges of the cut $F_H$. Furthermore, there is no guarantee that we can simply merge the immersion of the subgraphs together along the edges of $F_G$. It could be that the cut $F_H$ in $H$ allows for some connectivity between $H_1$ and $H_2$ that can not be replicated by the cut $F_G$ in $G$. Thus, instead of simply recursing into the smaller subgraph $H_1$ along an edge cut we need to somehow remember the relevant properties of $H_2$ and the cut $F_H$ in the smaller instance $H_1$. We refer to the data structure that will serve this purpose as an $\mathrm{\Omega }$-knitwork below.

We now present the framework of knitworks in more detail. Given a digraph $G$ and a strict subset $X\subset V(G)$, we let $\overline{X}≔V(G)\setminus X$ and call

the cut induced by $X$. We denote by ${\rho }^{-}(X)\subseteq \rho (X)$ the set of edges with head in $X$, and by ${\rho }^{+}(X)\subseteq \rho (X)$ the set of edges with tail in $X$. If $X=\{v\}$ is a single vertex we write $\rho (v)$ as well as ${\rho }^{-}(v)$ and ${\rho }^{+}(v)$ for simplicity. A rooted digraph is a tuple $(G,\pi ,X)$ where $G$ is a digraph, $X\subset V(G)$ is a strict subset and $\pi$ is a map assigning to $X$ a linear order $\pi (X)$ on $\rho (X)$.⁹⁹9In the full paper we actually root digraphs in several cuts induced by disjoint sets $X_1,\mathrm{\dots },X_{\mathrm{\ell }}$. Furthermore, we allow some vertices of degree one in $X$. We call these graphs quasi-Eulerian, as they are not strictly Eulerian anymore. This seems necessary for our inductive arguments. We tacitly ignore these details in this exposition.

Given a well-quasi-order $\mathrm{\Omega }=(V_{\mathrm{\Omega }},⪯)$ we define $\mathrm{\Omega }$-knitworks as follows. (Again, we omit some details for the sake of simplicity.) Given two disjoint sets $E_1,E_2$ we write $\mathrm{Match}(E_1,E_2)$ for the set of all possible matchings on $E_1\times E_2$, where a matching $M\subseteq E_1\times E_2$ is a set of pairs such that no element of $E_1\cup E_2$ is part of two distinct pairs in $M$.

The general idea of $\mathrm{\Omega }$-knitworks is that towards a proof of ˜3.1 our aforementioned strategy would be to inductively decompose the graphs along “small cuts” into structurally rich “pieces” (we will not make this precise here) and contract these pieces into placeholder vertices at which one encodes the information of the pieces they replace. This information will essentially be kept track of by the maps ${\mu }_{𝒢},{𝔪}_{𝒢}$ and ${\mathrm{\Phi }}_{𝒢}$. More precisely, the goal is to “cut out” pieces $P\subset V(G)$ of the graph that induce rooted Eulerian digraphs that fall into a class $𝒞$ for which we already proved that it is well-quasi-ordered by $\mathrm{\Omega }$-knitwork immersion. Let $\mathrm{\Omega }=(𝒞,\hookrightarrow )$ be the well-quasi-order on $𝒞$. We then replace these pieces with new vertices $p^{\ast }$, say, and mark these with the respective “immersion type” ${\mathrm{\Phi }}_{𝒢}(p^{\ast })≔{\sigma }_P\in 𝒞$ of the piece they replace. See Figure 2 for a schematic illustration, where $P$ represents such a “piece”, and $p^{\ast }$ is the corresponding placeholder vertex. The map ${\mu }_{𝒢}$ then fixes a linear order on the respective cut $\rho (P)=\rho (p^{\ast })$, so that the pieces we replaced can inductively be “glued back” together in the correct way. Finally, ${𝔪}_{𝒢}$ keeps track of the “allowed edge-disjoint routings” inside the pieces we cut out, where each matching $M\in {𝔪}_{𝒢}(p^{\ast })$ of such a placeholder vertex $p^{\ast }$ represents pairs of edges that can be simultaneously connected by edge-disjoint trails inside the piece $P$ it replaces. This guarantees that we do not wrongly create new connectivity (recall that immersion is defined in terms of edge-disjoint trails, and thus several trails may possibly pass through the same vertex). See Figure 2 where a routing of two edge-disjoint trails through $P$ is highlighted on the left side, and the respective matching consisting of two pairs of edges of the cut after replacing the piece by $p^{\ast }$ is highlighted on the right side.

We lift the definition of immersion of digraphs to immersion of $\mathrm{\Omega }$-knitworks. To this extent, we define sub-knitworks.

Note that by the third bullet point in Definition 4.1, ${𝔪}_{\mathscr{H}}(v)$ is as expected. Given sub-knitworks, the following is a (slightly incomplete) definition of $\mathrm{\Omega }$-knitwork immersion.

It is crucial to note that, as opposed to standard immersion of digraphs, for $\mathrm{\Omega }$-knitwork immersion, it makes a difference whether we let edges be mapped to paths or trails. The main reason being that the fourth bullet point in the definition of $\mathrm{\Omega }$-knitwork immersion above may not allow to reroute trails to paths at vertices; we come back to this below.

As a first step we verify that the above defined structure and containment relation are compatible, i.e., strong and weak $\mathrm{\Omega }$-knitwork immersion induce quasi-orders on $\mathrm{\Omega }$-knitworks.

Although tedious and lengthy, a proof of Lemma 4.4 is straightforward. Note here that for weak immersion, one cannot add the assumption for edges to be mapped to paths instead of trails as the proof would fail, contrasting standard immersion of digraphs.

We then continue by introducing the main tools to prove decomposition results, namely stitching and knitting. In a nutshell, given a rooted Eulerian digraph $(G,\pi ,X)$ and a set $X\subseteq Y\subset V(G)$ together with a linear order $\pi (Y)=\pi (\overline{Y})$ on $\rho (Y)$, we define the down- and up-stitches of $G$ at $Y$ to be the rooted Eulerian digraphs obtained when contracting $\overline{Y}$ and $Y$ into single vertices $y_{\ast }$ and $y^{\ast }$ respectively, keeping the roots $\pi (X)$ for the former, and fixing roots $\pi (y^{\ast })≔\pi (\overline{Y})$ for the latter. See Figure 3 for a schematic illustration. We say that $Y$ induces a rooted cut in $(G,\pi ,X)$.

Note here that $Y,\overline{Y}$ partition $V(G)$ and every incidence of an edge in $G$ with a vertex in $G$ is still part of one of the two stitches. In particular, it is straightforward to define stitches for $\mathrm{\Omega }$-knitworks since we do not alter any of the relevant incidences for ${\mu }_{𝒢}$, ${𝔪}_{𝒢}$, or ${\mathrm{\Phi }}_{𝒢}$. What we referred to as “cutting out pieces” above will essentially be handled by up- and down-stitching vertex sets inducing rooted cuts, where the down-stitches will essentially be the aforementioned “pieces”; we refer to the full paper for details.

Thus, stitching gives us a tool to decompose $\mathrm{\Omega }$-knitworks along partitions, where the newly introduced vertices obtained via stitching can be seen as the aforementioned placeholder vertices marking the cuts. We define knitting as a sort of inverse operation to stitching, where given two graphs $G$ and $H$, both with partitions $X,\overline{X}$ and $A,\overline{A}$, and linear orders $\pi (X)=\pi (\overline{X})$ and $\pi (A)=\pi (\overline{A})$ on $\rho (X)$ and $\rho (A)$ respectively, we knit $G$ and $H$ along the cuts $\rho (X)$ and $\rho (A)$ if the cuts are of equal order, moving to a new graph on $X\cup \overline{A}$ identifying $\rho (X)$ with $\rho (A)$ – with respect to the linear orders $\pi (X)$ and $\pi (A)$ – and keeping all the incidences with $X$ and those with $\overline{A}$. This will allow us to “knit back the pieces” we stitched off for inductive reasoning. Note that ${\mu }_{𝒢}$ keeps track of the respective linear orders when we cut out pieces inductively, and in future work we will essentially “knit back” the pieces with respect to ${\mu }_{𝒢}$ instead of $\pi (X)$.

We use both notions to prove two important results. First, the Stitch-and-Knit Lemma, which proves and makes precise what we mean by both operations being inverse to each other. It essentially states that, given an $\mathrm{\Omega }$-knitwork $𝒢$ and a rooted cut $Y\subset V(G)$ with a linear order $\pi (Y)=\pi (\overline{Y})$ on $\rho (Y)$, first taking the up- and down-stitches of $𝒢$ at $Y$, and then knitting them back together results in $𝒢$.

Second, applying the Stitch-and-Knit Lemma, we then prove a “decomposition theorem” marking a first main result. The exact formulation needs too many definitions hence we resort to the following intuitive description.

Intuitively speaking, the theorem proves that stitching and knitting are the right tools to inductively decompose $\mathrm{\Omega }$-knitworks and then prove that the resulting pieces can be immersed in each other, complementing the introductory discussion of this section. Although this seems clear at first glance, the proof is rather technical.

We then use Theorem 4.5 to prove decomposition “meta theorems”. Again fully stating the theorems would require a lot of machinery, but the main contribution can be intuitively understood as follows: “If we can decompose our graphs along small cuts in a tree-like fashion, then it suffices to prove that the resulting pieces of the trees are well-quasi-ordered”. We want to emphasise that this is not the exact statement of the theorem and there is a little extra work needed to prove this exact claim (which we defer to another paper as it does not fit the scope of this exposition), but it portrays the main idea behind that theorem without the need to introduce further technical definitions. These kind of decomposition meta theorems mark a crucial first step towards an inductive proof of ˜3.1, giving tools to reduce the conjecture on the more general graph class to that of “smaller well-behaved pieces”.

Finally, we want to emphasise that the above results are given in the realm of quasi-Eulerian digraphs, where the non-Eulerian vertices – recall that there may be vertices of degree one which we tacitly ignored – are assumed to be covered by the root sets, but there is technically no immediate restriction on the number of such vertices (but rather on the size of the cut induced by the root sets). Every digraph $D$ can easily be transformed into a quasi-Eulerian digraph as follows: Let $v\in V(D)$ with out-degree $k$ and in-degree $\mathrm{\ell }$, say $k>\mathrm{\ell }$, then add $t≔k-\mathrm{\ell }$ vertices $v_1^{+},\mathrm{\dots },v_t^{+}$ to $D$ and add the edges $(v_i^{+},v)$ for every $1\le i\le t$. Thus, it seems plausible that the results discussed above may be of independent interest for further non-Eulerian classes of digraphs that can be “decomposed” into quasi-Eulerian “pieces”; we leave this for future research.

The second, and possibly most direct main contribution of this paper is a proof that the class of Eulerian digraphs lacking “structural richness” with respect to strong immersion is indeed well-quasi-ordered. Formally, we prove the following.

Before we give the definition of carving width, we mention that Theorem 4.6 is equivalent to the following.

A carving of a digraph $G$ is a tuple $(T,\mathrm{\ell })$ where $T$ is a cubic tree and $\mathrm{\ell }:V(G)\to \mathrm{leaves}(T)$ is an injective map from $V(G)$ to the leaves of $T$. To every edge $e\in E(T)$ one can naturally associate an induced cut in $G$ as follows: let $T_1,T_2$ be the two components of $T-e$, and let $V_i≔{\mathrm{\ell }}^{-1}(\mathrm{leaves}(T_i))$ for $i=1,2$, then $V_1,V_2$ partition $V(G)$. In particular $\rho (V_1)=\rho (V_2)$ and we define the width of $e$ to be $|\rho (V_1)|$. Finally, the width of a carving is the maximum width over all its edges, and the carving width of a digraph $G$ is the minimum width over all possible carvings of $G$. Carvings for rooted digraphs and $\mathrm{\Omega }$-knitworks are defined analogously by defining it for the graph obtained from $\overline{G}$ after up-stitching $X$ into a single vertex $x^{\ast }$; we omit the exact definitions here.

Theorem 4.6, and hence Theorem 4.7, is a corollary of a much stronger theorem, proving that well-linked $\mathrm{\Omega }$-knitworks of bounded carving width are well-quasi-ordered by strong $\mathrm{\Omega }$-knitwork immersion, marking a first and crucial class of $\mathrm{\Omega }$-knitworks for which we prove a well-quasi-order result. An $\mathrm{\Omega }$-knitwork $𝒢$ is well-linked, if for every vertex $p\in \mathrm{dom}({𝔪}_{𝒢})$ it holds that for every pair of partitions $E_1^{-},E_2^{-}$ of ${\rho }^{-}(p)$ and $E_1^{+},E_2^{+}$ of ${\rho }^{+}(p)$ such that $|E_i^{-}|=|E_i^{+}|$ for $i=1,2$, there is a matching $M\in {𝔪}_{𝒢}(p)$ such that $M=M_1\cup M_2$ is the disjoint union of two perfect matchings $M_i\in \mathrm{Match}(E_i^{-},E_i^{+})$. Intuitively speaking, this means that for every such partition of $\rho (p)$ we can “link up” $E_1^{-}\cup E_2^{+}$ and $E_2^{-}\cup E_1^{+}$ “inside” the piece $P$ represented by $p$ via a respective set of edge-disjoint trails, i.e., every trail has as first edge one of $E_i^{-}$ and as last edge one of $E_i^{+}$ for $i=1,2$. See Figure 4 for a schematic illustration of two choices of partitions $E_1^{-},E_1^{+}$ highlighted in dark orange and $E_2^{-},E_2^{+}$ highlighted in dark blue, and the respective matchings in ${𝔪}_{𝒢}(p)$, or rather the sets of edge-disjoint trails in the associated piece $P$, highlighted in gray.

Recall that, as we briefly discussed above, it is crucial to define $\mathrm{\Omega }$-knitwork immersion using trails due to the fact that the immersion needs to respect the map ${𝔪}_{𝒢}$, which in turn keeps track of the allowed edge-disjoint routings at vertices. In particular, edge-disjoint trails respecting ${𝔪}_{𝒢}$ can in general not be rerouted to edge-disjoint paths respecting ${𝔪}_{𝒢}$. However, we prove that, given a well-linked $\mathrm{\Omega }$-knitwork $𝒢$ and a set of edge-disjoint trails $ℒ=\{L_1,\mathrm{\dots },L_k\}$ in the underlying directed graph $G$ such that for ever $1\le i\le k$, $L_i$ has one endpoint in a $A\subseteq V(G)$ and the other in $B\subseteq V(G)$, say, with $A\cap B=\mathrm{\varnothing }$, the trails in $ℒ$ can be rerouted to a set of edge-disjoint trails ${ℒ}^{\prime }=\{L_1^{\prime },\mathrm{\dots },L_k^{\prime }\}$ such that for every $1\le i\le k$, $L_i^{\prime }$ still has one endpoint in $A$ and the other in $B$ – not necessarily the same as $L_i$ – with the addition that ${ℒ}^{\prime }$ now respects ${𝔪}_{𝒢}$. More precisely, we prove the following.

This is a crucial result, allowing us to lift general “Menger-type” arguments on the underlying digraph $G$ to the $\mathrm{\Omega }$-knitwork $𝒢$. See Figure 5 for an illustration of a single step in the proof of Lemma 4.8, where $ℒ$ – on the left hand side – and ${ℒ}^{\prime }$ – on the right hand side – consist of two trails, one highlighted in orange and one in purple. ${ℒ}^{\prime }$ is obtained from $ℒ$ by rerouting at a single vertex $v$, highlighted by a large cycle, where one “feasible” matching in ${𝔪}_{𝒢}(v)$ is highlighted by a respective matching in the center of the cycle in the middle figure. The green highlighted trails “are remaining trails” – edge-disjoint from $ℒ$ and ${ℒ}^{\prime }$ respectively, in the respective figure – in the graph with both endpoints $v$, that exist using the Eulerianness of $G$.

Finally, a weaker version of the aforementioned theorem implying Theorem 4.6 reads as follows.

Outline of the Proof: The proof of the theorem builds on a well-known result due to Robertson and Seymour [27] – the so-called Tree Lemma – that has been refined by Geelen, Gerards, and Whittle [9] to a setting that fits our needs. Let us briefly elaborate on the overall proof technique. Forgetting about well-linked $\mathrm{\Omega }$-knitworks and focusing solely on Eulerian digraphs, the proof follows the same line of argumentation as those in [27] and [9]. That is, assume towards a contradiction that Theorem 4.6 is wrong, and let ${(G_i)}_{i\in \mathbb{N}}$ be a sequence of Eulerian digraphs of carving width $\le k$ refuting the theorem. For every $i\in \mathbb{N}$ let $(T_i,{\mathrm{\ell }}_i)$ be a respective carving of $G_i$ witnessing its width. Next root the trees $T_i$ at some vertex $x_i\in V(T_i)$, i.e., $T_i$ is a directed graph where every vertex except for $x_i$ has in-degree one, whereas $x_i$ has in-degree $0$. Let $e=(t_1,t_2)\in E(T_i)$ be a directed edge and define $T_i^1,T_i^2$ to be the components of $T_i-e$ containing $t_1$, respectively $t_2$; note that $x_i\in V(T_i^1)$. Then ${\mathrm{\ell }}^{-1}(V(T_i^1)),{\mathrm{\ell }}^{-1}(V(T_i^2))$ partition $V(G_i)$, and in particular $X(e)≔{\mathrm{\ell }}^{-1}(V(T_i^1))$ induces a cut in $G_i$, uniquely defined by $e$.

With these definitions at hand, intuitively speaking, the aforementioned Tree Lemma implies¹³¹³13This relies on many further technicalities, such as assuming the carvings to be linked. the existence of an infinite index set $I\subseteq \mathbb{N}$ and for every $i\in I$ a directed edge $e_i\in E(T_i)$ such that the sequence of Eulerian digraphs ${(G_i\mid e_i)}_{i\in I}$ obtained from $G_i$ by contracting $X(e_i)$ into a single vertex $x_i^{\ast }$, is an antichain with respect to strong immersion. Furthermore, for every choice $I^{\prime }\subseteq I$ and every choice $e_i^{\prime }\in E(T_i^{\prime })\setminus \{e_i\}$ the respective sequence of Eulerian digraphs ${(G_i\mid e_i^{\prime })}_{i\in I^{\prime }}$ is a chain with respect to strong immersion. Let $p_i$ be the head of $e_i$ for every $i\in I$, and let ${ℱ}_i\subseteq E(T_i^{\prime })$ be those edges that admit $p_i$ as a tail. By a well-known theorem due to Higman [10] we derive the existence of with $i,j\in I$ and an injection $\alpha :{ℱ}_i\to {ℱ}_j$ such that for every $f\in {ℱ}_i$ it holds that ${\eta }_f:G_i\mid f\hookrightarrow G_j\mid \alpha (f)$. Collecting the maps ${\eta }_f$ for $f\in {ℱ}_i$ one can then “combine” these strong immersions to construct a strong immersion $\eta :G_i\mid e_i\hookrightarrow G_j\mid e_j$ contradicting the fact that ${(G_i)}_{i\in \mathbb{N}}$ was an antichain.

We emphasise that the above sketch is far from complete. In particular, note that we are working with a far more complicated structure than Eulerian digraphs, and we need to carefully lift all of the mentioned results to $\mathrm{\Omega }$-knitworks: This is where the “well-linkedness” assumption will be crucial, and Lemma 4.8 will be needed.

Implications: The implications of Theorem 4.9 are three-fold. First, it immediately implies Theorem 4.6 by rooting the graphs in some arbitrary vertex and fixing the maps $\mu ,𝔪$ and $\mathrm{\Phi }$ to be nowhere defined. Note that, as discussed above, this marks one of the first more versatile directed graph classes – besides the aforementioned results on tournaments and extensions [5, 2] – for which a positive well-quasi-ordering result is known. And, complementing the introductory discussion, a class $𝒞$ of Eulerian digraphs of bounded carving width may still admit arbitrarily long alternating paths.

Secondly, the theorem is an important step towards a proof of ˜3.1, settling a crucial base case. Recall that our main strategy will be to decompose our graph into pieces that fall into classes for which we already proved well-quasi-ordering results. The inductive argument tries to cut out “structurally rich” pieces which are handled differently, where Theorem 4.6 essentially covers the case for pieces lacking “structural richness”. It turns out that for many containment relations that do not yield well-quasi-orders on (directed) graphs, they already fail to do so on classes of “structurally non-rich” (directed) graphs, the exact definition of which depends on the respective relation.

Thirdly, it can be seen as another decomposition “meta theorem” towards a proof of ˜3.1. To see this, note that Theorem 4.9 is much stronger than Theorem 4.6: Besides covering the base case, it proves that it is enough to decompose the graphs into possibly “structurally rich” pieces for which we already proved well-quasi-ordering, that are “loosely connected” to each other in a tree-like fashion. More precisely, if we loosen the definition of carving slightly by allowing the leaves of $T$ to correspond to sets of vertices partitioning $V(G)$, and manage to carve the digraphs of a class $𝒞$ in a way that the width of this carving is bounded by $k$ say, and such that the leaf-bags “induce” graphs (by taking up- and down-stitches for example) that fall into a class ${𝒞}^{\ast }$ for which we already proved well-quasi-ordering with respect to strong immersion, then we can contract the bags into single vertices which we then mark with the respective immersion-type of $({𝒞}^{\ast },\hookrightarrow )$ using the maps $𝔪,\mu$ and $\mathrm{\Phi }$. This essentially defines for every $G\in 𝒞$ an $\mathrm{\Omega }$-knitwork of carving width at most $k$, where $\mathrm{\Omega }=({𝒞}^{\ast },\hookrightarrow )$. By Theorem 4.9 $\mathrm{\Omega }$-knitworks of bounded carving width are well-quasi-ordered by strong immersion, and thus, assuming that the carving defined above is linked (a notion to be made precise), we derive that $𝒞$ is well-quasi-ordered. We will not elaborate on this further and leave this application to future work.

We want to mention here that very recently Lunel and Maria [21] independently derived a weaker variant of Theorem 4.6, i.e., they proved that “Eulerian embeddable”¹⁴¹⁴14The graphs are embedded in the plane such that for every vertex it’s in- and out-edges alternate given an orientation of the plane. $4$-regular Eulerian digraphs of bounded carving width (without labels or roots) are well-quasi-ordered by strong immersion. They proved this as their main technical lemma to prove that graphs embedded in ${ℝ}^2$ are well-quasi-ordered by embedded minors, providing another nice use case and relation of Eulerian digraphs to undirected graphs.

Finally, we conclude the paper with a result that complements Corollary 2.2 and ˜3.2; the following is a weaker version of the exact theorem.

Thus, the class $𝒞(2,4)$ of planar Eulerian digraphs of treewidth at most $2$, admitting at most one vertex of degree larger than $4$ is not well-quasi-ordered by strong immersion following Corollary 2.2, but it is well-quasi-ordered by weak immersion. This is a dichotomy result in the following sense: If we additionally bound the maximum degree of $𝒞(2,4)$, then the class is well-quasi-ordered with respect to both weak and strong immersion by Theorem 4.6. If we restrict to treewidth at most $1$, then it is not hard to see that this class is also well-quasi-ordered by both weak and strong immersion (it consists of bidirected trees, possibly with parallel edges).

We want to highlight that the proof of Theorem 4.10 uses a nice trick, linking the treewidth of the underlying undirected graph to the carving width of the directed graph (recall that this is, in general not possible if we do not impose restrictions on the degrees), which may be of independent interest. Theorem 4.10 further strengthens the evidence for ˜3.2. We note that we believe that the arguments in the proof of Theorem 4.10 can be leveraged (by a careful and rather involved analysis) to prove the theorem for up to three vertices of unbounded degree, but the general case of bounded treewidth requires a substantial and non trivial amount of work. Since the bounded treewidth case follows from more “natural” results – the proofs of which we are currently writing up – we omit a direct proof here as it is more cumbersome than insightful.