$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4+i$
vertices. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
be one of the two extreme vertices of that path. To obtain
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{i}$
from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{i+1}$,
we first delete
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$.
If this generate edges between vertices of degree two in the resulting graph,
then we contract these (one or two) edges. One can easily check that, in the
weak subdivision
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{W}_{4+i}$
of the wall, performing vertex deletions and edges contraction between degree-
two vertices along the top row and the left-most column, we can obtain
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{W}_{(3+i)\times(3+i)}$.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

######  Claim .

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathfrak{A}=\\{\mathcal{H}^{j}\mid
1\leq j\leq 5\\}$ is a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\leq_{\sf
wtp}$-antichain.

Proof of claim.

  1. 1.

Consider
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in[1,4]$.
It is well-known that the treewidth of any subdivision of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W_{i\times
i}$ is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$.
Observe that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i\in\mathbb{N}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tw}(H^{j}_{i})=2$. As
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G\leq_{\sf
wtp}H$ implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tw}(G)\leq{\bf tw}(H)$, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{j}\not\leq_{\sf
wtp}\mathcal{H}^{5}$. Moreover, if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G\leq_{\sf
wtp}H$, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{\sf
e}(G)\leq\Delta_{\sf e}(H)$. This implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{5}\not\leq_{\sf
wtp}\mathcal{H}^{j}$.

  2. 2.

We observe that a weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\theta_{i}$
is either the single vertex graph or a theta graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\theta_{i^{\prime}}$
for some
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i^{\prime}<i$.
It follows that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in\\{2,3,4\\}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{j}\not\leq_{\sf
wtp}\mathcal{H}^{1}$.

  3. 3.

We observe that every weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\theta}_{i}$
that is biconnected is either the single vertex graph or
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\theta}_{i^{\prime}}$
for some
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i^{\prime}<i$.
It follows that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in\\{1,3,4\\}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{j}\not\leq_{\sf
wtp}\mathcal{H}^{2}$.

  4. 4.

We observe that for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in\\{3,4\\}$,
every weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{i}$
that is biconnected is either the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{3}$,
the fan
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\varphi_{3}$
or contains an induced path on at least
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}5$
vertices. It follows that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j^{\prime}\in\\{1,2\\}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{j^{\prime}}\not\leq_{\sf
wtp}\mathcal{H}^{j}$.

  5. 5.

Finally, we observe that every weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{j}\in\mathcal{H}^{4}$
that is biconnected contains a vertex whose neighbors belong to a common path.
It follows that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{4}\not\leq_{\sf
wtp}\mathcal{H}^{3}$. We also observe that every biconnected weak topological
minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\varphi}_{j}$
that is not
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{3}$
nor the fan
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\varphi_{3}$,
contains a vertex of vertex-degree three whose neighbors all have vertex-
degree two. This implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{3}\not\leq_{\sf
wtp}\mathcal{H}^{4}$.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

######  Claim .

For every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}1\leq
j\leq 5$ and for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i\in\mathbb{N}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(H_{i}^{j})\geq\sqrt{i}$.

Proof of claim. To see this, observe that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in[1,5]$,
the parameterized set of graphs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{j}$
contains only biconnected graphs. Moreover for every graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{i}\in\mathcal{H}^{j}$,
we have
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\max\\{\Delta_{\sf
e}(H^{j}_{i}),{\bf tw}(H^{j}_{i})\\}\geq i$. It follows from Section 4 that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(H^{j}_{i})\geq\sqrt{i}$.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

######  Claim .

There exists a function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f:\mathbb{N}\rightarrow\mathbb{N}$
such that if for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in[1,5]$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{k}\not\leq_{\sf
wtp}G$, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(G)\leq f(k)$.

Proof of claim. By the parametric equivalence between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(G)$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}(G)=\max\big{\\{}\\{\Delta_{\sf
e}(B)\>|\>B\in{\sf bc}(G)\\}\cup\\{{{\bf tw}}(B)\>|\>B\in{\sf
bc}(G)\\}\big{\\}}$ (see Section 4), it suffices to prove that there exists a
function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f:\mathbb{N}\rightarrow\mathbb{N}$
such that if for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j\in[1,5]$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H^{j}_{k}\not\leq_{\sf
wtp}G$, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}(G)\leq
f(k)$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
be the block of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}(G)=\max\\{\Delta_{\sf
e}(B),{\bf tw}(B)\\}$. We have two cased to consider:

  * •

Suppose first that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}(G)={\bf
tw}(B)$. Observe that by the wall theorem (see [37, 12]), if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
contains a subdivision of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W_{k\times
k}$ as a subgraph, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tw}(G)\geq k^{{\cal O}(1)}$.

  * •

So let us consider the case where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}(G)=\Delta_{\sf
e}(B)$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
be a vertex of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
edeg}_{B}(x)=\Delta_{\sf e}(B)$ and suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
edeg}_{G}(x)\geq k\cdot k^{2k-3}$. As by assumption,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\theta_{k}\not\leq_{\sf
wtp}G$, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
vdeg}_{B}(x)\geq k^{2k-3}$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T^{\prime}$
be a (simple) subtree of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B\setminus\\{x\\}$
spanning all the neighbors of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$.
We consider the tree
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
obtained from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T^{\prime}$
by disolving every vertex of vertex-degree two that is not a neighbor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$.
It follows that every vertex of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
is a neighbor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
or a branching vertex. Observe that every vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
has vertex-degree
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
vdeg}_{T}(y)<k$, as otherwise we would have
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\theta}_{k}\leq_{\sf
wtp}G$. It follows that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
is a tree spanning at least
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k^{2k-3}$
vertices and its maximum vertex-degree
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{\sf
v}(T)$ is at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$.
Moreover, the number of vertices in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
is at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\Delta_{\sf
v}(T))^{{\lceil\sf diam}(T)/2\rceil}$, where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
diam}(T)$ is the diameter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$.
This implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
contains a path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
of length at least
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4k-6$.
Observe that the vertex set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(P)$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
is partitioned into
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{x}=V(P)\cap
N(x)$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{\overline{x}}=V(P)\cap\overline{N}(x)$.
Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|P_{x}|\geq|P_{\overline{x}}|$.
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$
be the subset of vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
containing every odd neighbor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$.
We have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|Y|\geq
k$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
be the graph with vertex set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(P)\cup\\{x\\}$
and containing the edges of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
and the edges between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
and the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$.
We observe that, by construction of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
and definition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{k}$
is a weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
and of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$:
contradiction. So let us assume that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|P_{x}|<|P_{\overline{x}}|$.
Observe that, by construction of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$,
every vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y\in
V(P)\cap\overline{N}(x)$ is a branching vertex. Thereby for every such vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
contains a path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{y}$
of length at least
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2$
between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y$.
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$
be the subset of vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
containing every odd vertex of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(P)\cap\overline{N}(x)$.
We have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|Y|\geq
k$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
be the graph containing the vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$,
the path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
and every path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{y}$
between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y\in
Y$. Again, we observe that, by construction of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
and definition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\varphi}_{k}$
is a weak topological minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
and of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$:
contradiction.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

As
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}$ is closed under weak topological minor (see Section 2), by Section 5, we
have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}_{\mathfrak{A}}(G)\leq{\bf
etw}(G)^{2}$. By Section 5, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(G)\leq\mathbf{p}_{\leq_{\sf
wtp},\mathfrak{A}}(G)^{4\cdot\mathbf{p}_{\leq_{\sf wtp},\mathfrak{A}}(G)+1}$.
It follows that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}\sim\mathbf{p}_{\leq_{\sf wtp},\mathfrak{A}}$. ∎

Let us discuss the exponential gap obtained above between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}_{\mathfrak{A}}$.
Consider the graph family
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{G}=\\{G_{3+i}\mid
k\in\mathbb{N}\\}$ where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}$
is defined as follows (see Figure 9). Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
be a tree of diameter
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2i+1$
such that every internal node has vertex-degree
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i+2$.
Then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}$
is obtained by adding a universal vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
to the leaves of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$,
and then by replacing every edge with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i+2$
multiple edges.

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
Figure 9: The graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{5}$
is obtained from the above graph by replacing every edge with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4$
multiple edges.

######  Observation .

For every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k\in\mathbb{N}$,
the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}$
does not contain as weak topological minor any of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\theta_{3+i}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\theta}_{3+i}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{3+i}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\varphi}_{3+i}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{W}_{(3+i)\times(3+i)}$.

###### Proof.

As every edge has multiplicity
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i+2$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\theta_{3+i}\not\leq_{\sf
wtp}G_{3+i}$. Since the vertex-degree of every vertex, but
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$,
is at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i+2$,
we also have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\theta}_{3+i}\not\leq_{\sf
wtp}G_{3+i}$. The diameter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}-x$
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2i+1$
while the diameter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{3+i}$
and of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{\varphi}_{3+i}$
are
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2i+2$.
It follows that that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{3+i}\not\leq_{\sf
wtp}G_{3+i}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\tilde{\varphi}_{3+i}\not\leq_{\sf
wtp}G_{3+i}$. Finally, observe that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}$
is a series-parallel graph (it has treewidth
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2$).
As a consequence,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\dot{W}_{(3+i)\times(3+i)}\not\leq_{\sf
wtp}G_{3+i}$. ∎

We observe that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{\sf
e}(G_{3+i})=2\times(i+1)^{i+1}$. On one hand, as
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{3+i}$
is biconnected and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tw}(G_{3+i})=2$, by Section 4, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}(G_{3+i})\geq\sqrt{\Delta_{\sf e}(G_{3+i})}$. On the other hand, by
Section 5, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}_{\mathfrak{A}}(G_{3+i})=3+i$.
This proves that the exponential gap between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}_{\mathfrak{A}}$
is tight.

### Incomparability between edge-treewidth and tree-cut width.

We now prove that the parameters of edge-treewidth and tree-cut width are
parametrically incomparable, i.e.,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tcw}\not\sim{\bf etw}$. For this, we may avoid giving the (lengthy) definition
of tree-cut width and use instead the main result of Wollan in [45] who proved
that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
tcw}\sim{\bf p}_{\leq_{\sf im},{\\{\cal W}\\}}$. Therefore it remains to show
why
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
p}_{\leq_{\sf im},{\\{\cal W}\\}}\not\sim{\bf etw}$. Notice that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
p}_{\leq_{\sf im},{\\{\cal W}\\}}(_{i})$ is trivially bounded for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$,
while the graphs in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}^{1}=\\{\theta_{3+i}\mid
i\in\mathbb{N}\\}$ have unbounded edge-treewidth, because of Section 5. This
implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
etw}\not\lesssim{\bf p}_{\leq_{\sf im},{\\{\cal W}\\}}$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Z_{i}$
be the graph obtained after taking
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|E(W_{i})|$
copies of 3 and then identifying one vertex of each copy to a single vertex.
It is easy to see that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W_{i}\leq_{\sf
im}Z_{i}$, therefore
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
p}_{\leq_{\sf im},{\\{\cal W}\\}}\geq i$. On the other side, each of the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|E(W_{i})|$
blocks of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Z_{i}$
has maximum edge-degree three, and therefore
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Z_{i}$
has bounded edge-treewidth, because of Section 4, which implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf
p}_{\leq_{\sf im},{\\{\cal W}\\}}\not\lesssim{\bf etw}$.

##  6 On the complexity of computing edge-treewidth

We discuss the computational complexity of the following decision problem:

Edge-Treewidth
---
_Input:_ |  A graph $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$ and an integer $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$.
_Question:_ |  Decide if $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\bf etw}(G)\leq k$?

######  Theorem
($\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
NP}$-completeness).

The problem Edge-treewidth is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
NP}$-complete.

###### Proof.

Clearly, the problem Edge-treewidth belongs to NP. Indeed given a layout
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
L}$ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$,
one can check in polynomial time if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbf{p}_{\delta^{\sf
ce}}(G,{\sf L})\leq k$. The
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
NP}$-hardness proof is based on a reduction from the Min-Bisection problem.

Min-bisection problem
---
_Input:_ |  A graph $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$ and an integer $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$.
_Question:_ |  Is there a bipartition $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1},V_{2}$ of $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(G)$ such that $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}||V_{1}|-|V_{2}||\leq 1$ and $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|E_{G}(V_{1})|\leq k$ ?

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
Figure 10: The graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
is obtained by adding to the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
an independent set of size
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n^{2}$
and making each of the vertices of the independent set universal to the
vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$.

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,k)$
be an instance of Min Bisection where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a graph on
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n$
vertices. We build an instance
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(H,w)$
of Edge-treewidth as follows (see Figure 10):

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(H)=V(G)\cup
Q$, where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is an independent set of size
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n^{2}$;

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(H)=E(G)\cup\\{\\{x,y\\}\mid
x\in V(G),y\in Q\\}$, that is we add to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(G)$
all possible edges between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(G)$
;

  * •

and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}w=\frac{n^{3}}{2}+k$.

######  Claim .

If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,k)$
is a YES-instance of Min-Bisection, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(H,w)$
is a YES-instance of Edge-treewidth.

Proof of claim. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1},V_{2}$
be a bipartition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(G)$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}||V_{1}|-|V_{2}||\leq
1$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|E_{G}(V_{1})|\leq
k$. Let us consider a layout
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
L}$ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
such that for every triple
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x,y,z\in
V(H)$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x\in
V_{1}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y\in
Q$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}z\in
V_{2}$, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x\prec_{{\sf
L}}y\prec_{{\sf L}}z$, (in other words
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\sf
L}=\langle V_{1}\cdot Q\cdot V_{2}\rangle$) (here we use
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\cdot$
for the sequence concatenation operation). Observe that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{{}^{\sf
ec}_{H,{\sf L}}(\frac{n}{2}+1)}\leq\frac{n^{3}}{2}+k=w$. Indeed,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S_{\frac{n}{2}+1}=Q\cup
V_{2}$ induces a connected subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$,
that is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C_{H}(S_{\frac{n}{2}+1},x_{\frac{n}{2}+1})=Q\cup
V_{2}$. Moreover, there are
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n^{2}\cdot\frac{n}{2}$
edges between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
and at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
edges between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}$.
Let us prove that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i\neq\frac{n}{2}+1$,
$\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L},i)\leq w$. We consider three
cases:

  * •

Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i\leq\frac{n}{2}$
(i.e.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x_{i}\in
V_{1}$). Observe that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C_{H}(S_{i},x_{i})=S_{i}$
and thereby
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(C_{H}(S_{i},x_{i}))$
contains
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(i-1)\cdot
n^{2}$ between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(H)\setminus
S_{i}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$,
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
edges between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(H)\setminus
S_{i}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S_{i}\setminus
Q$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\leq\frac{n^{2}}{2}$.
All in all, we have that $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf
L},i)\leq(i-1)\cdot n^{2}+\frac{n^{2}}{2}\leq(\frac{n}{2}-1)\cdot
n^{2}+\frac{n^{2}}{2}=\frac{n^{3}}{2}-\frac{n^{2}}{2}$.

  * •

Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i>n^{2}+\frac{n}{2}$
(i.e.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x_{i}\in
V_{2}$). A symmetric argument proves that $\color[rgb]{0.1,0.1,.34}{}^{\sf
ec}(H,{\sf L},i)\leq w$.

  * •

Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\frac{n}{2}+1<i\leq
n^{2}+\frac{n}{2}$ (i.e.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x_{i}\in
Q$). Then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(C_{H}(S_{i},x_{i}))$
contains at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
edges between the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(i-\frac{n}{2})\cdot\frac{n}{2}$
edges between the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}$,
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(n^{2}+\frac{n}{2}-i)\cdot\frac{n}{2}$
edges between the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$.
In total, we obtain that $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L},i)\leq
w$.

So we proved that $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L})\leq w$ and
thereby
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(H,w)$
is a YES-instance of Edge-treewidth.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

######  Claim .

If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(H,w)$
is a YES-instance of Edge-treewidth, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,k)$
is a YES-instance of Min-Bisection.

Proof of claim. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L$
be a layout of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
such that $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L})\leq
w=\frac{n^{3}}{2}+k$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k\leq\frac{n^{2}}{2}$.
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$
be the smallest index for which
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|(V(H)\setminus
S_{i})\cap V(G)|=|S_{i}\cap V(G)|=\frac{n}{2}$. We denote
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}=(V(H)\setminus
S_{i})\cap V(G)$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}=S_{i}\cap
V(G)$. Let us prove that the bipartition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1},V_{2}$
certifies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,k)$
is a YES-instance of Min-Bisection.

We first argue that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S_{i}\cap
Q\neq\emptyset$. For the sake of contradiction, suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S_{i}\cap
Q=\emptyset$. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j<i$
be the largest integer such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x_{j}\in
Q$. By the minimality of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$,
we know that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v_{i-1}\notin
Q$ and thereby
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j<i-1$.
We observe that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C_{H}(S_{j-1},x_{j-1}))=S_{j-1}$
and moreover
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q\setminus\\{v_{j}\\}\subseteq
V(H)\setminus S_{j}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|S_{i-1}\cap
V(G)|\geq\frac{n}{2}+1$. It follows that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(S_{j-1})$
contains at least
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(n^{2}-1)\cdot(\frac{n}{2}+1)$
edges, that is $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf
L},i)>\frac{n^{3}}{2}+\frac{n^{2}}{2}$, contradicting the assumption that
$\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L})\leq w=\frac{n^{3}}{2}+k$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k\leq\frac{n^{2}}{2}$.

As a consequence of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q\cap
S_{i}\neq\emptyset$, we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C_{H}(S_{i},x_{i})=S_{i}$.
This implies that at least half of the edges incident to a vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
belongs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(C_{H}(S_{i},x_{i}))$.
Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q\in
S_{i}$, then every edge between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
belongs to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(C_{H}(S_{i},x_{i}))$.
Suppose that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q\notin
S_{i}$, then every edge between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}$
belongs to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E_{H}(C_{H}(S_{i},x_{i}))$.
It follows that $\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L},i)\geq
n^{2}\cdot\frac{n}{2}=\frac{n^{3}}{2}$. As by assumption
$\color[rgb]{0.1,0.1,.34}{}^{\sf ec}(H,{\sf L},i)\leq\frac{n^{3}}{2}+k$, this
implies that there are at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
edges betwwen
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V_{2}$,
certifying that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,k)$
is a YES-instance of Min-Bisection.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\diamond$

Section 6 and Section 6 establish the NP-hardness of the Edge-treewidth
problem. ∎

## References

  * [1] S. Arnborg, D. G. Corneil, and A. Proskurowski.  Complexity of finding embeddings in a $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-tree.  SIAM J. Algebraic Discrete Methods, 8(2):277–284, 1987.  doi:10.1137/0608024.
  * [2] U. Bertelè and F. Brioschi.  On non-serial dynamic programming.  Journal of Combinatorial Theory, Series A, 14(2):137 – 148, 1973\.  doi:10.1016/0097-3165(73)90016-2.
  * [3] H. L. Bodlaender.  Dynamic programming on graphs with bounded treewidth.  In International Colloquium on Automata, Languages and Programming (ICALP), volume 317 of Lecture Notes in Computer Science, pages 105–118, 1988.  doi:10.1007/3-540-19488-6_110.
  * [4] H. L. Bodlaender.  A linear time algorithm for finding tree-decompositions of small treewidth.  SIAM Journal on Computing, 25:1305–1317, 1996.  doi:10.1137/S0097539793251219.
  * [5] H. L. Bodlaender.  A partial k-arboretum of graphs with bounded treewidth.  Theoretical Computer Science, 209(1):1 – 45, 1998.  doi:10.1016/S0304-3975(97)00228-4.
  * [6] H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk.  An $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{O}(c^{k}\cdot n)$ $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}5$-approximation algorithm for treewidth.  In Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 499–508, 2013.  doi:10.1109/FOCS.2013.60.
  * [7] H. L. Bodlaender, M. R. Fellows, and D. M. Thilikos.  Derivation of algorithms for cutwidth and related graph layout parameters.  Journal of Computer and System Sciences, 75(4):231 – 244, 2009\.  doi:10.1016/j.jcss.2008.10.003.
  * [8] H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks.  Approximating treewidth, pathwidth, frontsize, and shortest elimination tree.  Journal of Algorithms, 18(2):238 – 255, 1995.  doi:10.1006/jagm.1995.1009.
  * [9] H. L. Bodlaender and T. Kloks.  Efficient and constructive algorithms for the pathwidth and treewidth of graphs.  Journal of Algorithms, 21(2):358 – 402, 1996.  doi:10.1006/jagm.1996.0049.
  * [10] H. L. Bodlaender and D. M. Thilikos.  Treewidth for graphs with small chordality.  Discrete Applied Mathematics, 79(1):45 – 61, 1997.  doi:10.1016/S0166-218X(97)00031-0.
  * [11] H. L. Bodlaender and D. M. Thilikos.  Computing small search numbers in linear time.  In International Workshop on Parameterized and Exact Computation (IWPEC), volume 3162 of Lecture Notes in Computer Science, pages 37–48, 2004.  doi:10.1007/978-3-540-28639-4_4.
  * [12] C. Chekury and J. Chuzhoy.  Polynomial bounds for the grid-minor theorem.  Journal of the ACM, 63(5):40:1–40:65, 2016.  doi:10.1145/2820609.
  * [13] F. R. K. Chung.  On the cutwidth and the topological bandwidth of a tree.  SIAM Journal on Algebraic and Discrete Methods, 6(2):268–277, 1985\.  doi:10.1137/0606026.
  * [14] B. Courcelle.  The monadic second-order logic of graphs. I. recognizable sets of finite graphs.  Information and Computation, 85(1):12–75, 1990.  doi:10.1016/0890-5401(90)90043-H.
  * [15] B. Courcelle.  The monadic second-order logic of graphs I. recognizable sets of finite graphs.  Information and Computation, 85(1):12 – 75, 1990.  doi:10.1016/0890-5401(90)90043-H.
  * [16] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms.  Springer, 2014.  doi:10.1007/978-3-319-21275-3.
  * [17] N. D. Dendris, L. M. Kirousis, and D. M. Thilikos.  Fugitive-search games on graphs and related parameters.  Theoretical Computer Science, 172(1):233 – 254, 1997.  doi:10.1016/S0304-3975(96)00177-6.
  * [18] R. Diestel.  Graph theory.  Springer-Verlag, 2005.  doi:10.1007/978-3-662-53622-3.
  * [19] G. Ding and B. Oporowski.  On tree-partitions of graphs.  Discrete Mathematics, 149(1-3):45–58, 1996.  doi:10.1016/0012-365X(94)00337-I.
  * [20] R. G. Downey and M. R. Fellows.  Parameterized complexity.  Springer, 1999.  doi:10.1007/978-1-4612-0515-9.
  * [21] J. A. Ellis, I. H. Sudborough, and J. S. Turner.  The vertex separation and search number of a graph.  Information and Computation, 113(1):50 – 79, 1994.  doi:10.1006/inco.1994.1064.
  * [22] J. Flum and M. Grohe.  Parameterized complexity theory.  Texts in Theoretical Computer Science. Springer, 2006.  doi:10.1007/3-540-29953-X.
  * [23] R. Ganian, E.J. Kim, and S. Szeider.  Algorithmic applications of tree-cut width.  In International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 9235 of Lecture Notes in Computer Science, pages 348–360. Springer, 2015.  doi:10.1007/978-3-662-48054-0\\_29.
  * [24] R. Ganian and S. Ordyniak.  The power of cut-bases parameters for computing edge-disjoint paths.  Algorithmica, 83:726–752, 2021.  doi:10.1007/s00453-020-00772-w.
  * [25] R. Ganian, S. Ordyniak, and M.S. Ramanujan.  On structural parameterization of the edge disjoint paths problems.  Algorithmica, 83:1605–1637, 2021.  doi:10.1007/s00453-020-00795-3.
  * [26] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, 1978.
  * [27] A. C. Giannopoulou, M. Pilipczuk, J.-F. Raymond, D. M. Thilikos, and M. Wrochna.  Linear kernels for edge deletion problems to immersion-closed graph classes.  In International Colloquium on Automata, Languages, and Programming (ICALP), volume 80 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.57.
  * [28] R. Halin.  S-functions for graphs.  Journal of Geometry, 8:171–186, 1976.  doi:10.1007/BF01917434.
  * [29] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater.  Fundamentals of Domination in Graphs, volume 208 of Pure and applied mathematics.  Marcel Dekker, 1998.  doi:10.1201/9781482246582.
  * [30] S. B. Horton, R. G. Parker, and R. B. Borie.  On minimum cuts and the linear arrangement problem.  Discrete Applied Mathematics, 103(1):127 – 139, 2000.  doi:10.1016/S0166-218X(00)00173-6.
  * [31] R. Karp.  On the computational complexity of combinatorial problems.  Networks, 5(1):45–68, 1975.  doi:10.1002/net.1975.5.1.45.
  * [32] N. G. Kinnersley.  The vertex separation number of a graph equals its path-width.  Information Processing Letters, 42(6):345 – 350, 1992.  doi:10.1016/0020-0190(92)90234-M.
  * [33] E. Korach and N. Solel.  Tree-width, path-widt, and cutwidth.  Discrete Applied Mathematics, 43(1):97–101, 1993.  doi:10.1016/0166-218X(93)90171-J.
  * [34] T. Nishizeki, J. Vygen, and X. Zhou.  The edge-disjoint paths problem is NP-complete for series–parallel graphs.  Discrete Applied Mathematics, 115(1):177 – 186, 2001.  doi:10.1016/S0166-218X(01)00223-2.
  * [35] N. Robertson and P. D. Seymour.  Graph minors I. excluding a forest.  Journal of Combinatorial Theory, Series B, 35(1):39 – 61, 1983\.  doi:10.1016/0095-8956(83)90079-5.
  * [36] N. Robertson and P. D Seymour.  Graph minors III. planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49 – 64, 1984\.  doi:10.1016/0095-8956(84)90013-3.
  * [37] N. Robertson and P. D. Seymour.  Graph minors. V. Excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986\.  doi:10.1016/0095-8956(86)90030-4.
  * [38] N. Robertson and P. D. Seymour.  Graph minors VIII. the disjoint paths problem.  Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.  doi:10.1006/jctb.1995.1006.
  * [39] N. Robertson and P. D. Seymour.  Graph minors. XX. Wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.  doi:10.1016/j.jctb.2004.08.001.
  * [40] N. Robertson, P. D. Seymour, and R. Thomas.  Quickly excluding a planar graph.  Journal of Combinatorial Theory, Series B, 62(2):323–348, 1994\.  doi:10.1006/jctb.1994.1073.
  * [41] P. Scheffler.  A practical linear time algorithm for disjoint paths in graphs with bounded tree-width.  Technical Report 396/1994, FU Berlin, Fachbereich 3 Mathematik, 1994.
  * [42] P. D. Seymour and R. Thomas.  Graph searching and a min-max theorem for tree-width.  Journal of Combinatorial Theory, Series B, 58(1):22–33, 1993.  doi:10.1006/jctb.1993.1027.
  * [43] D. M. Thilikos, M. Serna, and H. L. Bodlaender.  Cutwidth I: A linear time fixed parameter algorithm.  Journal of Algorithms, 56(1):1 – 24, 2005.  doi:10.1016/j.jalgor.2004.12.001.
  * [44] D. M. Thilikos, M. Serna, and H. L. Bodlaender.  Cutwidth II: Algorithms for partial $\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}w$-trees of bounded degree.  Journal of Algorithms, 56(1):25 – 49, 2005.  doi:10.1016/j.jalgor.2004.12.003.
  * [45] Paul Wollan.  The structure of graphs not admitting a fixed immersion.  Journal of Combinatorial Theory Series B, 110:47–66, 2015.  doi:10.1016/j.jctb.2014.07.003.


# Conflict graphs of maximally planar subgraphs of Petersen family graphs

Joel Foisy<EMAIL_ADDRESS>Justin Raimondi<EMAIL_ADDRESS>Department of Mathematics, SUNY Potsdam, Potsdam, NY 13676

###### Abstract

The purpose of this paper is to show that all maximally planar subgraphs of
graphs in the Petersen Family have associated conflict graphs unbalanced. All
but three strong conflict graphs arising from Petersen Family Graphs are
unbalanced, and the three that are balanced all come from $K_{4,4}-e$.

00footnotetext: _Key words_ spatial graph, conflict graph, intrinsically
linked, linklessly embeddable00footnotetext: _MSC 2020_ 57M15, 05C10, 57K10,
05C22

This paper consists of details that complement the paper [1]. For more context
and definitions, please see that paper.

We will use the following well-known facts about planar graphs:

  1. 1.

A maximal planar subgraph of a connected graph is connected.

  2. 2.

Given an $S^{2}$ embedding of a 2-connected graph, every region is bounded by
a cycle (see, for example, [3]).

  3. 3.

Let $G$ be a graph and $M$ a subgraph of $G$ that is maximally planar ($M$ is
planar, but the insertion of any edge from $G-M$ into $M$ results in a
nonplanar graph). Then $M$ is a spanning subgraph of $G$. Equivalently, the
only possible $M-$fragments are individual edges.

######  Proposition 1.

There are two maximal planar subgraphs of $K_{6}$ and the strong conflict
graph for both is not balanced. These subgraphs are pictured in Figure 1

###### Proof.

The first maximal planar subgraph pictured results from removing three non-
adjacent edges, the second results from removing a path of length 3. We argue
that these are the only maximal planar subgraphs of $K_{6}$ (up to symmetry).
Consider the edges that are removed from $K_{6}$ to form a maximal planar
subgraph. Denote by $H$ the subgraph formed by these edges. If $H$ is
connected, then $H$ must contain a path of length 3, else all edges of $H$ are
incident to a common vertex, which implies that $K_{6}-H$ contains $K_{5}$,
and thus is non-planar. Thus, if $H$ is connected, the resulting maximal
planar subgraph is the second one pictured in Figure 1.

Suppose $H$ is not connected. If $H$ has 3 components, then the complement of
$H$ is the first maximal planar subgraph in Figure 1. Suppose $H$ has two
components. If each component contains 3 vertices, then $K_{6}-H$ contains
$K_{3,3}$ as a subgraph and is non-planar. Otherwise, one component contains 4
vertices and the other contains 2. The component with 4 vertices cannot
contain 2 disjoint edges, else $K_{6}-H$ is a subgraph of the first subgraph
pictured in Figure 1. It also cannot contain a triangle, as this would imply
that it also contained 2 disjoint edges. It follows that the component with 4
vertices must be a $Y$, but then $K_{6}-H$ contains a $K_{5}$ minor. Thus,
there is no $H$ with exactly 2 components. ∎

Figure 1: The two maximal planar subgraphs of $K_{6}$.

######  Proposition 2.

There are three maximal planar subgraphs of $K_{3,3,1}$, and the strong
conflict graph for each is not balanced. These subgraphs are pictured in
Figure 2.

###### Proof.

We partition the vertices of $K_{3,3,1}$ into $\\{v\\}$, $\\{a,b,c\\}$ and
$\\{x,y,z\\}$. The first maximal planar subgraph in Figure 2 results from
removing two non-adjacent edges between $\\{a,b,c\\}$ and $\\{x,y,z\\}$. No
nonisomorphic maximal planar subgraph results from the removal of two such
edges. Suppose another maximally planar subgraph results from removing exactly
two edges in $G-v$, both of which are incident to the same vertex. Without
loss of generality, suppose that an edge is removed from $a$ to $x$ and from
$b$ to $x$. Then we must also remove an edge between $v$ and $\\{a,b,c\\}$,
else the non-planar subgraph induced by $\\{v,y,z\\}$ and $\\{a,b,c\\}$ is
present. It follows that either the third graph pictured in Figure 2 results
(up to symmetry), or that the edges $(v,a)$ and $(v,b)$ are present, but the
edge $(v,c)$ is removed. If edge $(v,x)$ is removed, we get a graph equivalent
to a subgraph of the second graph in Figure 2. Otherwise, as the edge $(v,a)$
is present, then by contracting, we get a graph that contracts onto $K_{3,3}$,
by contracting the edge $(v,a)$, and making one partition $\\{(v,a),b,c\\}$
and the other $\\{x,y,z\\}$.

If more than three edges are removed from $K_{3,3,1}-v$, then we obtain a
graph equivalent to a subgraph of the first graph in Figure 2. Now suppose
exactly three edges have been removed from $K_{3,3,1}-v$, with all incident to
a common vertex (say, $x$). In order for the resulting graph to be planar, an
edge from $v$ to $\\{a,b,c\\}$ must also be removed. This results in a graph
isomorphic to a subgraph of the third graph pictured in Figure 2.

Finally, suppose that just one edge has been removed from $K_{3,3,1}-v$.
Without loss of generality, we may assume this edge is $(b,x)$. If $v$ is
connected to $x$ and to $b$, then the resulting graph is non-planar, even if
other edges are removed from $v$. Without loss of generality, suppose the edge
$(v,x)$ has been removed. If none of the edges $(v,a),(v,b)$ or $(v,c)$ is
removed, the resulting graph contains a $K_{3,3}$, by partitioning
$\\{a,b,c\\}$ and $\\{x,y,z\\}$. If $(v,a)$ or $(v,c)$ is removed, we obtain a
subgraph of the second graph in Figure 2. Otherwise, if only the additional
edge $(v,b)$ is removed, then the result is $K_{3,3,1}-\Delta$, which is non-
planar. Moreover, any additional removed edge will result in a subgraph of the
second graph pictured in Figure 2. This concludes our proof.

One can check (see Figure 2) that the conflict graphs of each maximally planar
subgraph is balanced. ∎

Figure 2: The three maximal planar subgraphs of $K_{3,3,1}$.

Before we discuss the maximal planar subgraphs of $G_{8}$, we introduce the
following:

######  Proposition 3.

Suppose $H$ is obtained from $G$ by a $\Delta-Y$ exchange. Let $S$ represent
the set of maximal planar subgraphs of $G$ that contain the triangle used in
the $\Delta-Y$ exchange. Let $S^{\prime}$ represent the set of graphs obtained
by a $\Delta-Y$ operation on an element from $S$. Then any maximally planar
subgraph of $H$ that contains the $Y$ must be a subgraph of an element of
$S^{\prime}$.

###### Proof.

The result follows from the well-known fact that the $Y-\Delta$ operation
preserves planarity. Let $P^{\prime}$ be a maximally planar subgraph of $H$
that contains the $Y$. By applying a $Y-\Delta$ operation on $P^{\prime}$, we
obtain a planar subgraph (say $P$) of $G$ that contains the triangle.
Furthermore, $P$ must be a subgraph of an element of $S$, as $S$ contains
every maximally planar subgraph of $G$. It follows that $P^{\prime}$ must be a
subgraph of an element of $S^{\prime}$.

∎

######  Proposition 4.

The fourteen maximally planar subgraphs of $G_{8}$ represented in Figure 3 and
Figure 4 represent all possible maximally planar subgraphs of $G_{8}$. Each
has an unbalanced strong conflict graph.

###### Proof.

We first note that in Figure 3, the vertex $w$ represents the $Y$ vertex of
$G_{8}$ that is obtained from doing a $\Delta-Y$ exchange on $K_{3,3,1}$. The
vertex $v$ represents the vertex of degree $5$ in $G_{8}$, and $\\{a,b,c\\}$
and $\\{x,y,z\\}$ represent the two partitions of size three in $K_{3,3,1}$
that would result if the $Y$ is swapped back to a triangle. The colored edges
in Figure 3 represent edges of $G_{8}$ that are removed to obtain the maximal
planar subgraph. If a maximal planar subgraph of $G_{8}$ contains all of the
$Y$ edges, then by Proposition 3 and Proposition 2 it must be a subgraph of
one of the second through seventh graphs pictured in Figure 3, or the first
graph, with edge $(a,y)$ put back in. We denote the first graph with edge
$(a,y)$ put back in $G^{\prime}$. It can be verified (see Figure 5) that the
second through eighth graphs are planar, and thus they must be maximally
planar. The graph $G^{\prime}$ requires the removal of an additional edge to
obtain a planar graph. If either edge $(b,x)$ or $(a,y)$ is removed, we get
the same (isomorphic) maximally planar subgraph of $G_{8}$, the first pictured
in Figure 3. If edge $(b,z)$ or $(c,y)$ or $(c,x)$ or $(z,a)$ is removed, we
obtain a subgraph of the second graph pictured. If an edge with $v$ as an
endpoint is removed, note that if both $(v,b)$ and $(v,y)$ are removed, we
still have a $K_{3,3}$ minor on $\\{v,c,z\\}$ and $\\{w,(b,x),(a,y)\\}$. As
there are no other non-$Y$ edges to remove, we have listed all possible
maximal planar subgraphs of $G_{8}$ obtained from subgraphs of $G^{\prime}$.

Figure 3: The representations of the seven maximal planar subgraphs of $G_{8}$
that include all edges of the $Y$ that would transform it back to $K_{3,3,1}$.

Now we consider maximal planar subgraphs that result from removing one or more
edges of the $Y$. We first consider exactly one edge being removed from the
$Y$. Suppose the edge removed is incident to $v$ (that is, edge $(v,w)$). A
maximal planar subgraph that has only edge $(v,w)$ removed from the $Y$ must
have a non $Y$ edge removed. First suppose no edge equivalent to $(b,y)$ has
been removed. An edge not incident to $v$ must be removed, so we may assume,
without loss of generality, that edge $(b,z)$ has been removed. The result is
maximally planar and is the third graph represented in Figure 4. Now suppose
edges $(v,w)$ and $(b,y)$ have been removed. The result is still nonplanar, so
one more edge must be removed. We obtain a maximally planar subgraph if
$(a,x)$, $(v,b)$, or $(v,y)$ is removed. These are the first and second cases
in Figure 4. To avoid the first three graphs in Figure 4, we assume that all
edges incident to $z$ and all edges incident to $c$ are present, as well as
edges $(a,x),(v,b),$ and $(v,y)$. To obtain a new, maximally planar subgraph,
we must remove either $(a,y)$ or $(b,x)$. If we remove both, we obtain a graph
isomorphic to a subgraph of the first graph in Figure 4. If we remove just,
say, $(a,y)$, then we also must remove edge $(v,a)$ to obtain a planar graph.
This result in a subgraph equivalent to a subgraph of the second graph in
Figure 4.

Now we suppose that only one edge of the $Y$ has been removed, and that edge
is not incident to $v$. Without loss of generality, we may assume that edge
$(c,w)$ has been removed. We note that if the edge $(b,y)$ (or equivalent) is
removed, we obtain the fourth maximally planar subgraph pictured in Figure 4.
If we instead removed edge $(v,y)$ (equivalently $(v,x)$), we obtain the fifth
maximally planar subgraph pictured in Figure 4. If we remove $(c,w)$ and
$(b,z)$ (or $(a,z)$), we obtain the sixth graph in Figure 4. Finally, we note
that if we removed the edges $(c,w),(c,y),(c,x),(v,b)$ and $(v,a)$, the result
would still be non-planar, as we would have $K_{3,3}$ subdivision with the
partitions: $\\{v,a,b\\}$ and $\\{x,y,z\\}$ (the edge between $v$ and $z$ is
subdivided.) As there are no other possible edges to remove, we have
classified all maximal planar subgraphs of $G_{8}$ that have exactly one $Y$
edge removed.

Now suppose exactly two $Y$ edges have been removed. Suppose first that
$(c,w)$ and $(w,z)$ have been removed. Further removing any edge incident to
$v$ results in a subgraph of the fifth graph in Figure 4. We similarly do not
obtain a maximally planar subgraph if we remove any other edge.

Now suppose exactly two $Y$ edges have been removed, where one edge is
incident to $v$. Without loss of generality, suppose $(v,w)$ and $(c,w)$ have
been removed. The only way we obtain a new maximally planar subgraph here is
to remove either edge $(v,b)$ or $(v,a)$. This case is represented as the
seventh graph in Figure 4.

Finally, a maximal planar subgraph cannot have all three $Y$ edges removed, as
this would result in a disconnected graph.

Figure 4: The representations of the maximal planar subgraphs of $G_{8}$ that
have removed edges of the $Y$ that would transform $G_{8}$ back to
$K_{3,3,1}$.

Figures 5 and 6 shows planar embeddings of all these maximal planar subgraphs,
together with their unbalanced conflict graphs.

Figure 5: The embeddings and strong conflict graphs of the seven maximal
planar subgraphs of $G_{8}$ from Figure 3. Note that the bottom graph pictured
is not 2-connected, but the conflict graph is the same regardless of planar
embedding. Figure 6: The embeddings and strong conflict graphs of the seven
maximal planar subgraphs of $G_{8}$ from Figure 4. Note that the bottom graph
pictured is not 2-connected, but the conflict graph is the same regardless of
planar embedding.

∎

######  Proposition 5.

The six maximal planar subgraphs of $G_{7}$ represented in Figure 8 represent
all possible maximal planar subgraphs of $G_{7}$. Each has an unbalanced
strong conflict graph.

###### Proof.

First, we note that as $G_{7}$ is obtained from $K_{6}$ by a single $\Delta-Y$
exchange, we may label the vertices of $G_{7}$ as $\\{1,2,3,4,5,6,7\\}$, where
vertex $7$ is of degree 3, and it is incident to vertices $4,5$ and $6$. We
consider various ways of removing edges to obtain a planar subgraph. First, we
consider if edges from the $Y$ have been removed. Note that removing all three
$Y$ edges will not result in a maximal planar subgraph, as the result is
disconnected. Suppose exactly one edge of the $Y$ has been removed, say edge
$(6,7)$. The result is a subdivision of $K_{6}$ with two adjacent edges
removed. It follows that removing an edge incident to $4$ or $5$ results in a
maximal planar subgraph (the first one pictured in Figure 8 and represented
schematically in Figure 7). So, we may assume that no edge incident to $4$ or
$5$ is removed. We also note that we must remove an edge between $\\{1,2,3\\}$
and $\\{4,5,6\\}$, else $K_{3,3}$ will be present as a subgraph. If an edge
incident to $6$ is removed, say $(3,6)$, then we must also remove an edge in
the cycle $(1,2,3)$. If we remove edge $(2,3)$ or $(1,3)$, we have obtained
the fifth graph pictured in Figure 8. Suppose we remove edge $(1,2)$. In order
to obtain a planar subgraph, we must also remove either $(1,6)$ or $(2,6)$.
The result is a subgraph of the fifth graph in Figure 8.

If exactly two edges of the $Y$ have been removed, then we still must remove
an edge between $\\{1,2,3\\}$ and $\\{4,5,6\\}$ to obtain a maximally planar
subgraph. In any way we do this, we obtain a subgraph of the first graph in
Figure 8.

We may now assume that no $Y$ edge has been removed. Given a maximally planar
subgraph $G^{\prime}$, if none of the edges in triangle $(1,2,3)$ have been
removed from $G_{7}$ to obtain $G^{\prime}$, then the edges removed must form
a subgraph of $G_{7}$ with either 1 or 3 components. Two components are not
possible, as $K_{6}$ with two non-adjacent triangles removed is non-planar,
and the $\Delta-Y$ move preserves non-planarity.

To obtain a planar graph, we must remove an edge between $\\{1,2,3\\}$ and
$\\{4,5,6\\}$. Without loss of generality, suppose that edge $(1,4)$ has been
removed. Moreover, we must remove at least two such edges, not both incident
to $1$, else there is a $K_{3,3}$ subgraph present, formed by the vertices
$\\{2,3,7\\}$ and $\\{4,5,6\\}$. By symmetry, we may consider two cases:

Case 1: Edges $(1,4)$ and $(3,6)$ have been removed. If we remove either edge
$(2,6)$, or edge $(1,6)$, or edge $(3,4)$, we get either of the second or
third maximal planar subgraphs pictured in Figure 8. In order for for the
removed edges to form a connected or 3 component subgraph, one of these edges
must be removed. This concludes Case 1.

Case 2: Edges $(1,4)$ and $(3,4)$ have been removed. If we remove an edge from
$\\{1,3\\}$ to $\\{5,6\\}$, then, up to equivalence, we get the third planar
subgraph in Figure 8, so we cannot remove those edges. If edge $(2,4)$ is
removed, then we still must remove another edge from $2$ to $\\{5,6\\}$ to get
a planar subgraph. In either case, we get the third planar subgraph in Figure
8. There is no other way to remove edges without making the subgraph on the
removed edges have exactly 2 components.

We may now assume our planar subgraph has at least one edge from $(1,2,3)$
removed (we still assume no edges of the $Y$ have been removed). We still must
remove a graph that has either 3 components or 1 component. The 3 component
graph is not possible, given that one of the three edges must come from the
triangle $(1,2,3)$. We note that at least 3 edges must be removed, or else by
performing a $Y-\Delta$ move, we get a planar subgraph of $K_{6}$ with fewer
than 3 edges removed, which is not possible, as shown earlier. We also note
that the removed edges cannot be contained in a triangle, else the resulting
graph is nonplanar. In order for $K_{3,3}$ not to be present, at least two
edges between $\\{1,2,3\\}$ and $\\{4,5,6\\}$ must be removed, not both
incident to the same vertex in $\\{1,2,3\\}$.Without loss of generality, we
may assume that edges $(1,4)$ and $(1,3)$ have been removed. We must remove
another edge, not incident to $1$. If $(3,6)$ and $(3,5)$ are removed, we get
the fourth graph pictured in Figure 8. The removal of $(3,4)$ won’t result in
a planar graph. If $(2,4)$ is removed, we get the equivalent of the last case
in Figure 8. The removal of $(2,5)$ or $(2,6)$ won’t result in a planar graph.
It follows that the only possible maximal planar graphs, for which an edge of
$(1,2,3)$ has been removed, are the fourth or sixth cases pictured in Figure
8.

Finally, we note that the conflict graph for all of the maximal planar
subgraphs of $G_{7}$ have unbalanced conflict graphs.

∎

Figure 7: Representations of the maximal planar subgraphs of $G_{7}$. Figure
8: The maximal planar subgraphs of $G_{7}$, with their conflict graphs.

######  Proposition 6.

Up to symmetry, there are precisely two maximal planar subgraphs of the
classic Petersen graph. Each has an unbalanced strong conflict graph.

###### Proof.

Recall that there is a well-known one-to-one correspondence between the
vertices of the Petersen graph and two element subsets of $\\{1,2,3,4,5\\}$,
and there is an edge between two vertices if and only if the corresponding two
element subsets are disjoint. From this, it readily follows that the symmetry
group is $S_{5}$. From the upper-left of Figure 9, we can see that
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{3,5\\},\\{1,4\\})\\}$ is maximally planar. By
symmetry, the following are also maximally planar: (via the permutation
$(1,2)(4,5)$: $PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{3,4\\},\\{2,5\\})\\}$, via the
permutation
$(4,5)$: $PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{3,4\\},\\{1,5\\})\\}$, and via the
permutation $(1,2)$:
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{3,5\\},\\{2,4\\})\\}$.

We can also see that $PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{2,5\\},\\{1,3\\})\\}$ is
maximally planar, and by symmetry the following are too: via $(4,5):$
$PG-$ $\\{(\\{1,2\\},\\{4,5\\}),(\\{1,3\\},\\{2,4\\})\\}$, via $(1,2)(4,5)$:
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{1,4\\},\\{2,3\\})\\}$, and via $(1,2)$:
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{2,3\\},\\{1,5\\})\\}$.

Note that the symmetry given by the permutation $(1,5)(2,4)$ takes
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{3,5\\},\\{1,4\\})\\}$ to
$PG-\\{(\\{1,2\\},\\{4,5\\}),(\\{2,5\\},\\{1,3\\})\\}$. Note also that given
an edge $e$ of $PG$, there are eight edges that are non-adjacent to $e$, and
are connected to $e$ by a single edge. There are 2 edges that are not adjacent
to $e$ and they are connected to $e$ by a shortest path of length $2$.
Further, given two adjacent edges, $e$ and $e^{\prime}$, the edges that are
distance two from $e$ are disjoint from the set of edges that are distance 2
from $e$. For the edge $e=(\\{1,2\\},\\{4,5\\}$, in the previous two
paragraphs we have accounted for removing another non-adjacent edge that is
connected by a single edge to the original–the result is always a maximal
planar subgraph. The other two non-adjacent edges to $(\\{1,2\\},\\{4,5\\})$
are $(\\{2,5\\},\\{1,4\\})$ and $(\\{1,5\\},\\{2,5\\})$. Removing $e$ and
either of these two edges results in a maximally planar subgraph. The
permutation $(4,5)$ interchanges either of these two edges paired with $e$. We
have a total of two maximal planar subgraphs of PG thus far.

Are there other maximal planar subgraphs of $PG$? By symmetry, we may assume
that the first edge removed is $e$ from above. We must remove an edge adjacent
to $e$, say $e^{\prime}$, to get a possibly different maximally planar
subgraph. Removing the one edge that is incident to both $e$ and $e^{\prime}$
will not result in a planar subgraph, as then $PG$ would be apex (that is,
becomes planar after the removal of a vertex), and hence not intrinsically
linked, which is a contradiction (see [2]). It follows that we must remove an
edge that is not adjacent to either $e$ or $e^{\prime}$. By the observation in
the previous paragraph, this edge cannot be distance 2 from both. It follows
that our resulting graph is not maximally planar.

Finally, we see in Figure 9 that the conflict graph for each of these three
maximally planar subgraphs is not balanced.

Figure 9: The maximally planar subgraphs of the Petersen graph. Note that the
top two cases are equivalent. In each case, the associated strong conflict
graph is not balanced.

∎

######  Proposition 7.

The seven subgraphs represented in Figure 10 are all of the maximal planar
subgraphs of $K_{4,4}-e$. Each has an unbalanced conflict graph.

###### Proof.

We denote the vertices of $K_{4,4}-e$ by the two partitions $\\{1,2,3,8\\}$
and $\\{5,6,7,4\\}$, where the edge removed is $(4,8)$.

First, we consider maximal planar subgraphs of $K_{4,4}-e$ where no edges of
either $Y$ is removed. Such maximal planar subgraphs must result from first
removing either three non-adjacent edges or a path of length 3, as $Y-\Delta$
exchanges preserve planarity, and otherwise the result would be a nonplanar
subgraph of $K_{6}$. By checking directly, the two resulting subgraphs are
planar, and again they must be maximally planar by the classification of
maximally planar subgraphs of $K_{6}$. This covers the fourth and sixth cases
in Figure 10.

No suppose that no edges of one $Y$ have been removed, but at least one edge
of the other $Y$ has been removed. Any such subgraph, after a $Y-\Delta$
exchange, results in a planar subgraph of $G_{7}$. By considering the maximal
planar subgraphs of $G_{7}$ that do not have any edges of the triangle that is
vertex-disjoint from the $Y$, we may conclude, without loss of generality,
that for any such maximally planar subgraph of $K_{4,4}-e$, the edges $(1,4)$
and $(2,5)$ have been removed. To get a planar subgraph, we must remove at
least one other edge between $\\{1,2,3\\}$ and $\\{5,6,7\\}$. No matter what
edge we get, up to symmetry, we get either the first or fifth maximally planar
subgraph depicted in Figure 10.

Finally, we suppose that at least one edge of each $Y$ has been removed. To
obtain a planar subgraph, we must also remove at least one edge between
$\\{1,3\\}$ and $\\{5,6,7\\}$. It follows that the resulting graph is
equivalent to either the second, third, or last maximally planar subgraph in
Figure 10.

It follows that, up to symmetry, the maximally planar subgraphs of $K_{4,4}-e$
represented in Figure 10 are all of the maximally planar subgraphs of
$K_{4,4}-e$.

Finally, as Figure 11 indicates, every maximal planar subgraph of $K_{4,4}-e$
has an unbalanced conflict graph.

Figure 10: Shorthand representations of maximal planar subgraphs of
$K_{4,4}-e$. Figure 11: Conflict graphs associated to maximal planar subgraphs
of $K_{4,4}-e$.

We now justify that the conflict graphs in Figure 11 are legitimate, in
particular the implicit (anti-)conflicts. First, for the top graph,
contracting edge $(2,4)$ allows the red fragment to ambient isotope to the
face bounded by cycle $(1,6,4-2,7)$, as the red shares endpoints with the
other fragments. This allows blue and green to implicitly anti-conflict.

For the last graph in Figure 11, we note first that red and blue strongly
anti-conflict, and red and green strongly conflict. As part of the conflict
graph process, we build a potentially flat embedding (see [1]) starting with
the given maximal planar subgraph embedding, and place the red and blue
fragments on the same side of the sphere containing the maximal planar
subgraph. The green fragment will be placed on the other side of the sphere.
We first note that the red and blue fragments can be thought of as forming a
tangle from knot theory (see [1] proof of Theorem 3.2 for terminology and more
references). Since the tangle connects NE to SW and NW to SE, it follows that
the tangle formed by the red and blue fragments is ambient isotopic to either
the rational tangle +1 or -1 (see [1] proof of Theorem 3.2 and Figure 12).

Figure 12: The two tangles possible for a potentially flat embedding.

If blue and red form +1, then by contracting edge $(4,2)$, the red fragment
can slide onto the sphere (into the face bounded by cycle $(2,7,3,5)$) so that
blue and green anti-conflict. If blue and red form -1, then by contracting
edge $(4,2)$, red slides into the face bounded by $(2,7,3,5)$ and again blue
and green anti-conflict. Since blue and green anti-conflict for every possible
potentially flat embedding with red and blue on the same side and blue and
green on the opposite side, then blue and green implicitly anti-conflict.

For the third graph, for a potentially flat embedding, red and blue are on the
same side, with green on the other side. Similar to the last graph, red and
blue form a tangle that must be equivalent to either +1 or -1. If the tangle
is +1, then contracting edge $(4,2)$ allows blue to land in the face bounded
by $(7,2,5,3)$ and red and green anti-conflict. If the tangle is -1, then a
nonsplit link is present: $(4,2,3,7)$ and $(1,5,8,6)$. As we have considered
all possible potentially flat embeddings, this shows that red and green
implicitly anti-conflict.

For the fifth graph, in a potentially flat embedding, the red and blue will be
on the same side (as well as green). Similar to the last case and third case,
the red and blue form a tangle that can be closed up two ways: connecting via
paths $(5,3,6)$ and $(2,7,8)$ or through $(2,5)$ and $(8,6)$. Again, in a
potentially flat embedding, the tangle must be equivalent to +1 or -1 (for
consistency, we will consider the green fragment as having endpoints at NW and
SE). Then +1 will be the tangle for which, after contracting edge $(7,8)$,
blue can deform to the face bounded by $(2,5,3,7)$. This contraction yields a
conflict between green and red. The link being equivalent to $-1$ would have
guaranteed a nonsplit link present involving blue, red, and the maximal planar
graph: namely $(1,6,2,4)$ and $(5,3,7,8)$. It follows that green and red
implicitly anti-conflict. ∎

######  Proposition 8.

The six graphs in Figure 13 represent, up to isomorphism, all possible maximal
planar subgraphs of $G_{9}$ with exactly two edges removed.

###### Proof.

We label the vertices of $G_{9}$ as $\\{0,1,2,3,4,5,6,7,8\\}$, where $(0,7,8)$
forms the only triangle, and if that triangle is removed, and the resulting
degree 2 vertices are smoothed out, the resulting $K_{3,3}$ has $\\{1,3,5\\}$
in one partition and $\\{2,4,6\\}$ in the other. We first consider maximal
planar subgraphs that have exactly two edges removed. Note that we cannot
remove exactly two triangle edges and obtain a planar graph. If one triangle
edge is removed, say $(0,7)$, then the only way to obtain a planar graph is to
remove either $(1,4)$ or $(2,3)$ (see the fourth graph in Figure 13). If we
remove an edge adjacent to $(0,7)$, then the result has to be nonplanar. The
only remaining options are to remove, say $(3,6)$ (contract $(3,7)$ and
$(8,6)$ to get $K_{3,3}$) or to remove $(6,8)$, in which case we can contract
edge $(0,1)$ and $(3,7)$ to get $K_{3,3}$ with partitions $\\{1,3,5\\}$ and
$\\{2,4,8\\}$.

Now suppose no triangle edge has been removed. Suppose edge $(0,1)$ has been
removed first. If we remove $(2,3)$ (equivalently $(2,5)$), $(3,6)$
(equivalently $(4,5)$) or $(4,7)$ (equivalently $(6,8)$), we obtain a
maximally planar subgraph (see the first three graphs in Figure 13). Let us
consider what other non-adjacent, non-triangle, edges can be removed. If we
remove $(3,7)$ (equivalently $(5,8)$), we obtain $K_{3,3}$ by contracting
$(0,7)$. The two partitions are $\\{5,6,(0,7)\\}$ and $\\{2,4,8\\}$ (note that
“edges” from $6$ pass through the vertex $1$). There are no other possible
non-adjacent, non-triangle edges that we can remove.

Finally, suppose no triangle edges are removed, nor any edges incident to the
triangle. Suppose, without loss of generality, that edge $(1,4)$ has been
removed. If we remove edge $(2,3)$, the result is planar. This is also true if
we remove the edge $(2,5)$ (equivalently, $(3,6)$)–see the last two graphs
shown in Figure 13. Thus, we have shown every maximally planar subgraph of
$G_{9}$ with exactly two edges removed. We note that the strong conflict graph
for each is an unbalanced bigon.

Figure 13: The maximal planar subgraphs of $G_{9}$ with exactly two edges
removed.

∎

######  Proposition 9.

The four graphs in Figure 14 represent, up to isomorphism, all possible
maximal planar subgraphs of $G_{9}$ with exactly three edges removed.
Moreover, the 10 graphs pictured in Figures 13 and 14 represent all possible
maximal planar subgraphs of $G_{9}$.

###### Proof.

We first note that Figure 14 shows four maximally planar subgraphs of $G_{9}$
with three edges removed.

Suppose a maximal planar subgraph of $G_{9}$ resulted from removing all edges
of the triangle. In order to obtain a planar subgraph, an additional edge must
be removed. If a 3-3 (where 3 refers to the degree of the vertices in $G_{9}$)
edge is removed, then we obtain a subgraph of the fourth graph pictured in
Figure 13. If a 3-4 edge is removed, we again obtain a subgraph of the third
graph pictured in Figure 14. Thus, a maximal planar subgraph must contain at
least one triangle edge.

Suppose exactly two triangle edges have been removed, say $(0,7)$ and $(7,8)$.
If we remove a $3-3$ edge, then again, we obtain the fourth graph in Figure
13, unless the edge removed is $(1,6)$ or $(2,5)$. If both are removed, we
obtain a subgraph of the fifth graph in Figure 13. Otherwise, if we remove
only one such edge, the result in non-planar. If we remove a 3-4 edge, we
obtain the third graph in Figure 14, unless we remove $(3,7)$ or $(7,4)$. If
we do remove $(0,7),(7,8),(3,7),$ and $(7,4)$, the result is non-planar. If we
remove both a $3-3$ and a $3-4$ edge, say, both $(4,7)$ (or $(3,7)$) and
$(2,5)$ (or $(1,6)$), then we obtain the equivalent of a subgraph of the
second graph in Figure 13.

By the argument in the previous paragraph, we may assume that no more than 1
triangular edge has been removed.

Figure 14: The maximal planar subgraphs of $G_{9}$ with exactly three edges
removed. Note the conflict graph for the first would be the same even if re-
embedded.

Now we suppose that exactly one triangle edge has been removed, say $(0,7)$.
If we further removed $(1,4)$ or $(2,3)$, we would obtain the fourth graph
pictured in Figure 13. Suppose no edge adjacent to $(0,7)$ has been removed.
If we only remove edge $(3,6)$ (equivalently, $(4,5),(1,6)$ or $(2,5)$), then
the result is non-planar. If we remove another edge non-adjacent to $(0,7)$,
we obtain a subgraph of either the fourth, fifth or sixth graph in Figure 13.
So now we assume that $(0,7)$ and an additional edge has been removed, with
the removed edge adjacent to $(0,7)$ (and not from the triangle). Without loss
of generality, suppose edge $(1,0)$ has been removed. The result of removing
$(0,7)$ and $(1,0)$ is nonplanar, so at least one more edge must be removed.
If edge $(3,7)$ is removed, we obtain the second graph pictured in Figure 14.
Removing edge $(0,2)$ results in a disconnected graph. Removing $(7,4)$ or
$(8,6)$ results in a subgraph of the third graph in Figure 13. Removing any
edge between two degree 3 vertices results in a subgraph of either the first,
second, or third graphs in Figure 13, or the first in Figure 14. Finally,
removing only edge $(5,8)$ results in a graph that is still nonplanar with
partitions $\\{2,6,7\\}$ and $\\{3,(8,0),(1,4,5)\\}$ forming a $K_{3,3}$
subdivision.

Finally, we suppose that no triangle edges have been removed. To get a new
maximally planar subgraph, at least 3 edges must be removed, and they cannot
all be incident to the same vertex (else the result is nonplanar). If we
remove any two vertex disjoint 3-3 edges, the result is either the fifth or
sixth graph in Figure 13. Similarly, if we remove disjoint $3-4$ and $3-3$
edges, the result is either the first or second graphs pictured in Figure 13.
If we remove exactly two disjoint $3-4$ edges, either we get the third graph
in Figure 13, or we get a nonplanar graph. Without loss of generality, suppose
$(0,1)$ and $(3,7)$ have been removed. The resulting graph is non-planar. If
we remove another $3-4$ edge, we get either a subgraph of the third graph in
Figure 13, or a subgraph of the last graph in Figure 14. If we remove another
$3-3$ edge, we get either a subgraph of the first or second graphs in Figure
13.

As this covers all cases, we have shown that the graphs in Figure 13 and
Figure 14 represent all possible maximally planar subgraphs of $G_{9}$. We
note that the associated strong conflict graphs are all unbalanced. ∎

## Acknowledgments

This work started as an REU project with students Cara Nickolaus, Justin
Raimondi, Joshua Wilson and Liang Zhang. We wish to thank the SUNY Potsdam-
Clarkson University REU Program and the NSA and NSF for financial support
under NSA Grant H98230-11-1-0206 and NSF Grant DMS-1004531. We would like to
thank Dr. Tom Zaslavsky and Dr. Garry Bowlin for helpful conversations.

## References

  * [1] Foisy, Joel: A spatial version of Tutte’s conflict graph, preprint, 2023.
  * [2] Sachs, Horst: On spatial representations of finite graphs, finite and infinite sets (Eger, 1981), eds. A Hajnal, L. Lovasz and V. T. Sos, Colloq. Math. Soc. Janos Bolyai, Vol. 37 (North-Holland, Budapest, 1984), 649–662.
  * [3] West, Douglas, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.