#  Branchwidth is $(1,g)$-self-dual††thanks:  Emails of authors:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Georgios Kontogeorgiou Mathematics Institute, University of Warwick, CV4 7AL,
UK Alexandros Leivaditis Mathematical Institute, Universiteit Leiden,
Netherlands Kostas I. Psaromiligkos Department of Mathematics, University of
Chicago, Chicago, IL, USA Giannos Stamoulis LIRMM, Univ Montpellier, CNRS,
Montpellier, France and Inter-university Postgraduate Programme “Algorithms,
Logic, and Discrete Mathematics” (ALMA). Supported by the French-German
Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027). Dimitris Zoros
Department of Mathematics, National and Kapodistrian University of Athens,
Athens, Greece.

###### Abstract

A graph parameter is self-dual in some class of graphs embeddable in some
surface if its value does not change in the dual graph by more than a constant
factor. We prove that the branchwidth of connected hypergraphs without bridges
and loops that are embeddable in some surface of Euler genus at most $g$ is an
$(1,g)$-self-dual parameter. This is the first proof that branchwidth is an
additively self-dual width parameter.

Keywords: branchwidth, duality, self-dual parameters, surface-embeddable
graphs, matroid branchwidth.

##  1 Introduction

A _surface_ is a connected compact 2-manifold without boundaries. A surface
$\Sigma$ can be obtained, up to homeomorphism, by adding $\mathbf{eg}(\Sigma)$
_crosscaps_ to the sphere and $\mathbf{eg}(\Sigma)$ is called the _Euler
genus_ of $\Sigma$. An _embedding of a graph_ $G$ on a surface $\Sigma$ is a
drawing of $G$ on $\Sigma$ without edge crossings. The _Euler genus_ of a
graph is the smallest number $g\in\mathbb{N}$ such that $G$ can be embedded on
a surface of Euler genus $g$. See the monograph by Mohar and Thomassen [14]
for more on graphs on surfaces.

The _dual graph_ of a graph $G$ embedded on a surface $\Sigma$ is the graph
$G^{*}$ embedded on $\Sigma$ that is obtained by considering a vertex $f^{*}$
for each face $f$ of $G$ and an edge $e^{*}$ for every edge $e$, where
$e^{*}=\\{f_{1}^{*},f_{2}^{*}\\}$ and $f_{1},f_{2}$ are the faces of $G$ to
which $e$ is incident (if $f_{1}=f_{2}$, then $e^{*}$ is a loop). Note that
$G^{*}$ can be embedded on $\Sigma$ by drawing each vertex $f^{*}\in V(G^{*})$
in the interior of the face $f$ of $G$ and every $e^{*}\in E(G^{*})$ crossing
the edge $e$ of $G$ exactly once. We call $e^{*}$ the _dual edge_ of $e$.

######  Definition 1.

Let $\Sigma$ be a surface and $\Lambda_{\Sigma}$ the set of all finite graphs
embedded on $\Sigma$. A function $f:\Lambda_{\Sigma}\rightarrow{\mathbb{N}}$
is called $(a,b)$-self-dual if for every $G\in\Lambda_{\Sigma}$ it holds that
$f(G^{*})\leq a\cdot f(G)+b$.

Self-duality of graph parameters like treewidth, pathwidth, or branchwidth has
played a fundamental role in the proof of Wagner’s conjecture by Robertson and
Seymour [18] and has been used to design polynomial-time approximation
algorithms for these parameters [3].

Treewidth has attracted most of the research concerning self-duality of graph
parameters. Lapoire proved [10], using algebraic methods, that treewidth is
$(1,1)$-self-dual in planar graphs, settling a conjecture stated by Robertson
and Seymour [16]. Shorter proofs of this result were given by Bouchitté,
Mazoit, and Todinca [4] and Mazoit [11], exploiting the properties of minimal
separators in planar graphs. Later, Mazoit [12] showed that treewidth is
$(1,g+1)$-self-dual in graphs of Euler genus at most $g$.

In the case of pathwidth, Fomin and Thilikos [5] proved that it is a
$(6,6g-2)$-self-dual parameter in graphs polyhedrically embedded on surfaces
of Euler genus at most $g$. This result was improved for planar graphs by
Amini, Huc, and Pérennes [1] who showed that pathwidth is $(3,2)$-self-dual in
3-connected planar graphs and $(2,1)$-self-dual in planar graphs with a
Hamiltonian path.

Concerning branchwidth (see Subsection 2.1 for a formal definition of the
branchwidth of a graph), Seymour and Thomas [20] proved that it is
$(1,0)$-self-dual in planar graphs that are not forests (for more direct
proofs, see also [13] and [7]). For graphs of Euler genus at most $g$, Sau and
Thilikos [19] proved that branchwidth is $(6,2g-4)$-self-dual in graphs of
Euler genus at most $g$. As mentioned in [19], one can show the
$(\frac{3}{2},g+2)$-self-duality of branchwidth in graphs of Euler genus at
most $g$, by combining using the $(1,g+1)$-self-duality of treewidth in graphs
of Euler genus at most $g$ [12] and the fact that for every graph $G$ with at
least three edges,
$\mathbf{bw}(G)\leq\mathbf{tw}(G)+1\leq\frac{3}{2}\mathbf{bw}(G)$ [17], where
$\mathbf{bw}(G)$ and $\mathbf{tw}(G)$ denote the branchwidth and the treewidth
of $G$, respectively. Sau and Thilikos conjectured [19] that branchwidth is
$(1,g)$-self-dual.

We prove this conjecture for connected graphs of Euler genus at most $g$
without bridges and loops. A _bridge_ of a graph is an edge whose deletion
disconnects the graph, while a _loop_ is an edge whose endpoints are the same
vertex.

######  Theorem 1.

The branchwidth of connected graphs of Euler genus at most $g$ without bridges
and loops is $(1,g)$-self-dual.

The proof of Theorem 1 is presented in Section 2. Our approach is to first
show that the _matroid branchwidth_ of a connected bridgeless graph of Euler
genus at most $g$ is $(1,g)$-self-dual. The matroid branchwidth of a graph $G$
is a parameter defined in [13], which we denote by
$\mu\text{-}\mathbf{bw}(G)$, and evaluates over branch decompositions of $G$,
whose width is not measured in terms of border size of a bipartition of the
edge set (like branchwidth) but using the _matroid connectivity function_ [15]
on this bipartition (see Subsection 2.2 for formal definitions). After proving
the $(1,g)$-self-duality of matroid branchwidth on connected bridgeless graphs
of Euler genus at most $g$, to prove Theorem 1 one can use the fact that
$\mathbf{bw}(G)=\mu\text{-}\mathbf{bw}(G)$, if $G$ is connected and bridgeless
[13] (see Proposition 2). Theorem 1 is stated for loopless graphs because, in
order to guarantee that $\mathbf{bw}(G^{*})=\mu\text{-}\mathbf{bw}(G^{*})$,
one has to ensure that $G^{*}$ is bridgeless, and the latter is true if $G$
has no loops (see Lemma 6).

#### From graphs to hypergraphs.

Theorem 1 also extends to hypergraphs. Before stating the result, let us give
some additional definitions on embeddings of hypergraphs and their duals. A
_hypergraph_ is a pair $(V,E)$ of sets, where the elements of $E$ are non-
empty subsets of $V$. We call the set $E$ the set of _hyperedges_ of $(V,E)$.

An _open arc_ $A$ on a surface $\Sigma$ is a subset of $\Sigma$ homeomorphic
to $(0,1)$. The set of its _endpoints_ is defined to be the set
$\bar{A}\setminus A$, where $\bar{A}$ denotes the closure of $A$. A connected
subset $X$ of a surface $\Sigma$ is a _star_ if it contains a point $v_{x}$
called its _center_ such that $X\setminus\\{v_{x}\\}$ is a union of pairwise
disjoint open arcs called _half-edges_. The set of _endpoints of a star_ is
the set $\bar{X}\setminus X$. An _embedding $\Lambda$ of a hypergraph $G$_ on
a surface $\Sigma$ is a subset of $\Sigma$ consisting of two disjoint sets,
$V_{G}$ and $E_{G}$, where $V_{G}$ is a set of points of $\Sigma$ associated
bijectively with the vertices of $G$ and $E_{G}$ is a set of pairwise disjoint
stars associated bijectively with the hyperedges of $G$ such that the
endpoints of a star are associated with the elements of the hyperedge that is
associated with said star. We will be using a common symbol for both the
hypergraph and its embedding. A _face_ of an embedded hypergraph $G$ is a
connected component of $\Sigma\setminus G$.

The _dual of a hypergraph_ $G$ embedded on $\Sigma$ is a hypergraph $G^{*}$
which has exactly one vertex lying in the interior of each face of $G$ and
exactly one star $s^{*}$ aligned over each star $s$ of $G$ such that their
centres coincide and the endpoints of $s^{*}$ (which may in pairs coincide)
are the vertices of $G^{*}$ lying in those faces of $G$ that are incident to
$s$ (these also may in pairs coincide). We now state our main result in its
full generality.

######  Theorem 2.

The branchwidth of connected hypergraphs, without loops and bridges, that are
embeddable on a surface of Euler genus at most $g$ is $(1,g)$-self-dual.

The proof of Theorem 2 uses Theorem 1 as a base case. In fact, we first show
that the branchwidth of a hypergraph and its _incidence graph_ are the same
(Lemma 7) and the same holds after considering its dual (Lemma 8). Then,
Theorem 2 follows by applying Theorem 1 for the incidence graph.

##  2 $(1,2g)$-self-duality of branchwidth on graphs

In this section we aim to prove Theorem 1. We first give the formal
definitions of a branch decomposition of a symmetric set function, of
branchwidth, and of the matroid branchwidth of a graph (Subsection 2.1 and
Subsection 2.2). We then show how the matroid branchwidth of a graph changes
when removing or contracting certain edges under different connectivity
assumptions (Subsection 2.3). Using these results, in Subsection 2.4, we show
that the contraction of a non-loop edge of a given graph (which corresponds to
the removal of its dual edge in the dual graph) preserves the same “gap”
between the matroid branchwidth of a graph and the one of its dual, under the
assumption that the dual edge of the contracted edge is not a bridge of the
dual graph. We conclude this section with the proof of Theorem 1, that is
presented in Subsection 2.5. At this point, we would like to stress that, in
this paper, we allow graphs to contain multiple edges and/or loops.

###  2.1 Branch decompositions and branchwidth

We first define branch decompositions of symmetric set functions. Here, we use
terminology from [6] and [21].

#### Branch decompositions.

Given a set $A$, we use $2^{A}$ to denote the set of all its subsets. Let $A$
be a finite set. A _branch decomposition_ on $A$ is a pair $(T,\lambda)$,
where $T$ is a binary tree and $\lambda$ is a bijection from $A$ to the set of
its leaves, denoted by $L(T)$. For every edge $e\in E(T)$, let $T_{1},T_{2}$
be the two connected components of $T\setminus e$. Notice that if we set
$A_{i}^{e}=\\{\lambda(v)^{-1}\mid v\in L(T)\cap V(T_{i})\\}$ for
$i\in\\{1,2\\}$, then $(A_{1}^{e},A_{2}^{e})$ is a partition of $A$. Let
$f:2^{A}\to\mathbb{R}$ be a symmetric set function (i.e., for every $B\in
2^{A}$, $f(B)=f(A\setminus B)$). For every $e\in E(T)$, we define
$f_{\lambda}(e):=f(A_{1}^{e})$ (note that this is well-defined since $f$ is
symmetric). The _width of $f$_ on a branch decomposition $(T,\lambda)$ on $A$,
denoted by $w_{f}(T,\lambda)$, is the maximum over all $e\in E(T)$ of
$f_{\lambda}(e)$. The _branchwidth of $f$ on $A$_ is the minimum width of $f$
over all branch decompositions $(T,\lambda)$ on $A$.

#### Branchwidth.

Given a hypergraph $G$ and a set $E\subseteq E(G)$, we define the _border_ of
$E$ as the largest subset of $V(G)$ whose each element is the end of both an
edge of $E$ and an edge of $E(G)\setminus E$ and is denoted by $\partial(E)$.
We use $\delta$ to denote the function that maps each $F\subseteq E(G)$ to
$|\partial(F)|$. The _branchwidth_ of $G$ is the branchwidth of $\delta$ on
$E(G)$ and is denoted by $\mathbf{bw}(G)$. We will use the term _branch
decomposition of $G$_ to refer to a branch decomposition of $E(G)$.

#### Connected branch decompositions.

A branch decomposition is _connected_ when for every $e\in E(T)$, both
$A_{1}^{e}$ and $A_{2}^{e}$ induce a connected subgraph of $G$. We will use
the following result [13, Theorem 1] (see also [2, Lemma 1] for a proof for
graphs).

######  Proposition 1.

Every connected bridgeless hypergraph $H$ has a connected branch decomposition
of width $\mathbf{bw}(H)$.

#### Duals of branch decompositions.

Let $G$ be a graph embedded on a surface. The _dual of a branch decomposition_
$(T,\lambda)$ of $E(G)$ is a branch decomposition $(T,\lambda^{*})$ on
$E(G^{*})$ where for every $v\in L(T)$, $\lambda^{*}(v)$ is the dual edge of
the edge $\lambda(v)$.

###  2.2 Matroid branchwidth

In this subsection, we define the _matroid branchwidth_ of a graph. Our
definition is from [13]. See [9, 8] for the corresponding notion of _matroid
pathwidth_.

#### Cycle bases of graphs.

A _cycle basis_ of a graph $G$ is a minimal set $C$ of cycles such that every
Eulerian subgraph of $G$ (i.e., a subgraph containing a cycle which uses each
edge of the subgraph exactly once) can be expressed as the symmetric
difference of cycles in $C$. The number of cycles in every cycle basis of $G$
is constant and equal to $|E(G)|-|V(G)|+\mathsf{cc}(G)$, wherein
$\mathsf{cc}(G)$ is the number of connected components of $G$. This number is
called the _circuit rank_ of $G$.

Given a hypergraph $G$ and a set $E\subseteq E(G)$, _a spanning forest of $E$_
is a maximal acyclic subset of $E$. We call _size_ of a spanning forest the
number of edges it contains. Given a graph $G$, we define the function
$r:2^{E}\to\mathbb{N}$ such that for every $E\subseteq E(G)$, $r(E)$ is the
size of a spanning forest of $E$.

#### Matroid branchwidth.

Let $G$ be a hypergraph. We define the function
$\mu_{G}:2^{E(G)}\to\mathbb{N}$, where for every $F\subseteq E(G)$,
$\mu_{G}(F):=r(F)+r(E(G)\setminus F)-r(E(G))+1$. The _matroid branchwidth_ of
$G$, denoted by $\mu\text{-}\mathbf{bw}(G)$, is the branchwidth of $\mu_{G}$
on $E(G)$. As observed in [13], while branchwidth and matroid branchwidth are
two different parameters and, in general,
$\mu\text{-}\mathbf{bw}(G)\leq\mathbf{bw}(G)$, Proposition 1 implies that in
the case of connected bridgeless hypergraphs, branchwidth and matroid
branchwidth coincide.

######  Proposition 2.

For every connected bridgeless hypergraph $H$,
$\mathbf{bw}(H)=\mu\text{-}\mathbf{bw}(H)$.

Note that, in matroid language, $r(E(G))$ is the rank of the graphic matroid
of $G$ (i.e., the matroid whose ground set is $E(G)$ and independent sets are
the edge sets of the forests of $G$). Therefore, the matroid branchwidth of
$G$ coincides with the branchwidth of the cycle matroid of $G$ (i.e., the
matroid that has $E(G)$ as ground set, while its independent sets are the sub-
forests of $G$). This provides an immediate proof for the planar case of
Theorem 1, since the branchwidth of a planar matroid is equal to that of its
dual. However, this cannot be extended to a general proof of our hypothesis in
higher Euler genus graphs, as the only matroids that are at the same time
graphic and co-graphic are planar matroids.

###  2.3 Matroid branchwidth and graph operations

In this subsection we show how the matroid branchwidth of a graph changes when
removing or contracting certain edges under different connectivity
assumptions. First, we give some definition and notation for edge removals and
contractions on graphs.

#### Operations on graphs.

Given a graph $G=(V,E)$ and a set $F\subseteq E$, we use $G\setminus F$ to
denote the graph $(V,E\setminus F)$ and, given an $e\in E$, we use $G\setminus
e$ to denote the graph $(V,E\setminus\\{e\\})$. We also denote by $G[F]$ the
graph $(V\cap F^{2},F)$. The _edge contraction_ of an edge $e=\\{u,v\\}$ of a
graph $G$ is the operation that deletes $e$, adds a new vertex $x_{uv}$ to $V$
and connects $x_{uv}$ to all the neighbours of $u$ and $v$ (notice that, as we
consider multigraphs, this operation may create multiple edges, and that a
contraction of an edge makes a triangle into a _dipole_ , and a dipole into a
loop). We denote the graph obtained by $G/e$. Given a set $F\subseteq E(G)$
and an edge $e=\\{u,v\\}\in F$, we denote by $F^{/e}$ the set obtained from
$F$ after the contraction of $e$, i.e., the set $(F\setminus(\bigcup_{z\in
N_{G}(u)\cup N_{G}(v)}\\{\\{u,z\\},\\{v,z\\}\\}))\cup\bigcup_{z\in
N_{G}(u)\cup N_{G}(v)}\\{x_{uv},z\\}$.

#### Contracting an edge of a connected graph.

We observe that, given a connected graph $G$, the graph $G/e$ is still
connected and has one fewer vertex than $G$. Also, for every connected graph
$H$ it holds that $r(E(H))=|V(H)|-1$. This implies the following.

######  Observation 1.

If $G$ is a connected graph, then $r(E(G/e))=r(E(G))-1$.

We also prove that given a graph $G$ and a set $F\subseteq E(G)$ such that
both $G$ and $G[F]$ are connected, the contraction of an edge in $F$ can
reduce $\mu_{G}(F)$ by one.

######  Lemma 1.

Let $G$ be a connected graph embedded on a surface and let $F\subseteq E(G)$
such that $G[F]$ is connected. For every $e\in F$, it holds that
$\mu_{G}(F)-1\leq\mu_{G/e}(F^{/e})\leq\mu_{G}(F)$.

###### Proof.

We show how $\mu_{G}(F)$ changes after the contraction of $e$. Observe that
since $G$ and $G[F]$ are connected, then, due to Observation 1,
$r(E(G/e))=r(E(G))-1$ and $r(F^{/e})=r(F)-1$. To see how $r(E(G)\setminus F)$
changes, observe the following: if $e\nsubseteq\partial(F)$, then
$E(G)\setminus F=E(G/e)\setminus F^{/e}$ and therefore $r(E(G/e)\setminus
F^{/e})=r(E(G)\setminus F)$. If $e\subseteq\partial(F)$, note that the
endpoints of $e$ may lie in the same component of $G\setminus F$ and therefore
the size of a spanning forest of the graph obtained by $G\setminus F$ can be
reduced by one after contracting $e$, implying $r(E(G)\setminus F)-1\leq
r(E(G/e)\setminus F^{/e})\leq r(E(G)\setminus F)$. ∎

#### Contracting non-loop edges of a connected bridgeless graph.

In the next lemma we show that, given a graph $G$ that is connected and
bridgeless (as the graphs in Theorem 1) and a set $F\subseteq E(G)$, where $F$
and $E(G)\setminus F$ induce connected graphs, the contraction of a non-loop
edge $e\in F$ reduces $\mu_{G}(F)$ by one if and only if both endpoints of $e$
belong to the border $\partial(F)$ of $F$. Otherwise, $\mu_{G}(F)$ remains the
same.

######  Lemma 2.

Let $G$ be a connected graph and let $F\subseteq E(G)$, where both $G[F]$ and
$G\setminus F$ are connected. For every non-loop $e\in F$, it holds that

$\mu_{G/e}(F^{/e})=\begin{cases}\mu_{G}(F)-1,&\text{if both endpoints of $e$
belong to $\partial(F)$ and}\\\ \mu_{G}(F),&\text{otherwise.}\end{cases}$

###### Proof.

Let $e$ be a non-loop $e\in F$. We show how $\mu_{G}(F)$ changes after the
contraction of $e$. First, observe that since $G$ and $G[F]$ are connected,
Observation 1 implies that $r(E(G/e))=r(E(G))-1$ and $r(F^{/e})=r(F)-1$.
Finally, if both endpoints of $e$ are contained in $\partial(F)$, we have that
$r(E(G/e)\setminus F^{/e})=r(E(G)\setminus F)-1$. To see this, observe that,
since both endpoints of $e$ are contained in $\partial(F)$ (and therefore both
endpoints are incident to edges in $E(G)\setminus F$) and $G\setminus F$ is
connected, the graph obtained from $G\setminus F$ after the contraction of $e$
is connected and has one fewer vertex than $G\setminus F$. If at least one of
the endpoints of $e$ is not contained in $\partial(F)$, then the fact that
$e\in F$ implies that the contraction of $e$ does not change the graph
$G\setminus F$, and thus $r(E(G/e)\setminus F^{/e})=r(E(G)\setminus F)$. ∎

#### Removing non-bridge edges.

We conclude this subsection by showing that, given a graph $G$ and a set
$F\subseteq E(G)$, the removal of an edge $e\in F$ that is not a bridge of $G$
reduces $\mu_{G}(F)$ by one if and only if $e$ is a bridge of $G[F]$.
Otherwise, $\mu_{G}(F)$ remains the same.

######  Lemma 3.

Let $G$ be a graph and let $F\subseteq E(G)$. For every $e\in F$ that is not a
bridge of $G$, it holds that

$\mu_{G\setminus e}(F\setminus e)=\begin{cases}\mu_{G}(F)-1,&\text{if $e$ is a
bridge of $G[F]$ and}\\\ \mu_{G}(F),&\text{otherwise.}\end{cases}$

###### Proof.

Let $e$ be an edge in $F$ that is not a bridge of $G$. We show how
$\mu_{G}(F)$ changes after the removal of $e$. In fact, we show that

  1. 1.

$r(E(G\setminus e))=r(E(G))$,

  2. 2.

$r(E(G\setminus e)\setminus(F\setminus e))=r(E(G)\setminus F)$, and

  3. 3.

$r(F\setminus e)=r(F)-1$ if $e$ is a bridge of $G[F]$, while $r(F\setminus
e)=r(F)$, otherwise.

Item (2) is directly implied by the fact that $e\in F$. Indeed,
$r(E(G\setminus e)\setminus(F\setminus
e))=r((E(G)\setminus\\{e\\})\setminus(F\setminus\\{e\\})=r(E(G)\setminus F)$.
For items (1) and (3), recall that, by definition, for every set $B\subseteq
E(G)$, $r(B)$ is equal to the number of edges of a spanning forest of $G[B]$.
Let $B\subseteq E(G)$. Observe that if $e$ is a bridge of $G[B]$ then every
spanning forest $T$ of $G[B]$ contains $e$ and therefore every spanning forest
$T^{\prime}$ of $(G\setminus e)[B\setminus e]$ has one edge less than $T$,
implying that $r(B\setminus e)=r(B)-1$. If $e$ is not a bridge of $G[B]$, then
every spanning forest of $(G\setminus e)[B\setminus e]$ is also a spanning
forest of $G[B]$, implying that $r(B\setminus e)=r(B)$. Item (1) follows by
setting $B=E(G)$ and using the assumption that $e$ is not a bridge of $G$,
while item (3) follows by setting $B=F$. ∎

###  2.4 On the duality of bridges and borders

We now aim to study when for a given set $F\subseteq E(G)$, whether $e^{*}$
being a bridge of $G^{*}[F^{*}]$ implies that both endpoints of $e$ belong to
$\partial(F)$, and vice-versa. We will use the following result from [14].

######  Proposition 3 ([14]).

Let $\Sigma$ be a surface of Euler genus $g$ and let $\\{C_{1},...,C_{k}\\}$
be a set of distinct closed arcs of $\Sigma$. If
$\Sigma\setminus\bigcup_{i\in[k]}C_{i}$ is connected, then $k\leq g$.

We show that if an $e\in F$ is non-loop and $e^{*}$ is a bridge of
$G^{*}[F^{*}]$, both endpoints of $e$ belong to $\partial(F)$.

######  Lemma 4.

Let $G$ be a graph embedded on a surface. Let $F\subseteq E(G)$ and let $e$ be
a non-loop edge in $F$. If $e^{*}$ is a bridge of $G^{*}[F^{*}]$, then both
endpoints of $e$ belong to $\partial(F)$.

###### Proof.

Suppose towards a contradiction that $e^{*}$ is a bridge of $G^{*}[F^{*}]$ and
that there is an endpoint $v$ of $e$ such that $v\notin\partial(F)$. Let $E$
be the set of edges of $G$ that have $v$ as an endpoint. The fact that
$v\notin\partial(F)$ implies that $E\subseteq F$. Now notice that since $e$ is
not a loop, $|E|\geq 2$. Moreover, since $e^{*}$ is a bridge of
$G^{*}[F^{*}]$, $e^{*}$ has two distinct endpoints (i.e., is not a loop),
which we denote by $x$ and $y$. Then, consider the graph
$G^{*}[E^{*}\setminus\\{e^{*}\\}]$ and observe that it is connected.
Therefore, the graph $G^{*}[E^{*}]$, which is a subgraph of $G^{*}[F^{*}]$,
has a cycle that contains $e^{*}$ in its edge set, a contradiction. ∎

Suppose that $e^{*}$ is not a bridge of $G^{*}[F^{*}]$, and thus is contained
in a cycle of $G^{*}[F^{*}]$. That does not necessarily mean that $e$ is in a
cut set of $G$, hence it might well be that $e\subseteq\partial(F)$, without
that meaning that $E(G)\setminus F$ has somehow become disconnected. However,
we can prove the following.

######  Lemma 5.

Let $G$ be a graph embedded on an surface of Euler genus $g$. Let $F\subseteq
E(G)$ such that $G\setminus F$ is connected. If $G^{*}[F^{*}]$ has a cycle
basis $\mathcal{C}$ where $|\mathcal{C}|>g$, there is an $e\in F$ such that
$e^{*}$ belongs to a cycle of $\mathcal{C}$ and $e$ is not a subset of
$\partial(F)$.

###### Proof.

Let $\Sigma$ be the surface of Euler genus $g$ on which $G$ is embedded. Let
$\mathcal{C}=\\{C_{1},\ldots,C_{\ell}\\},$ where $\ell>g$, be a cycle basis in
$G^{*}[F^{*}]$. According to Proposition 3,
$\Sigma\setminus\bigcup_{i\in[\ell]}C_{i}$ is disconnected. Then there is an
edge $e^{*}$ belonging to a cycle $C_{i}\in\mathcal{C}$ that bounds two
distinct faces (that cycle might be $e^{*}$ itself, if $e^{*}$ is a loop) and
let $f$ and $f^{\prime}$ be the two distinct faces that are incident to the
edge $e^{*}$ in $G^{*}$. Keep in mind that there is no arc in
$\Sigma\setminus\bigcup_{i\in[|\mathcal{C}|]}C_{i}$ starting from a point in
$f$ and finishing to a point in $f^{\prime}$. Note that $e^{*}\in F^{*}$ and
therefore $e\in F$. Let $u$ and $v$ be the endpoints of $e$, such that
$v^{*}=f$ and $u^{*}=f^{\prime}$. We will show that $\\{v,u\\}$ is not a
subset of $\partial(F)$. Suppose towards a contradiction that both $u$ and $v$
are incident to edges of $E(G)\setminus F$. Since $v,u\in V(G\setminus F)$ and
$G\setminus F$ is connected, there should be a path in $G\setminus F$
connecting $u$ and $v$. This implies that there is an arc in $\Sigma$ starting
from a point inside $u^{*}=f$ and finishing to a point inside
$v^{*}=f^{\prime}$ that does not cross any vertex of $G^{*}$ and any edge of
$F^{*}$. This contradicts the fact that
$\Sigma\setminus\bigcup_{i\in[\ell]}C_{i}$ is disconnected and $f$ and
$f^{\prime}$ are in two distinct connected components of
$\Sigma\setminus\bigcup_{i\in[\ell]}C_{i}$. ∎

Before concluding this subsection, we show that if $G$ is an embedded graph
without loops, then its dual $G^{*}$ has no bridges.

######  Lemma 6.

Let $G$ be a graph embedded on an surface. If $G$ has no loops, then $G^{*}$
has no bridges.

###### Proof.

Suppose, towards a contradiction, that $G$ has no loops and $G^{*}$ has a
bridge $e^{*}$. Let $f_{1}^{*},f_{2}^{*}$ be the endpoints of $e^{*}$ and note
that since $e^{*}$ is a bridge (and therefore not a loop) $f_{1}^{*}$ and
$f_{2}^{*}$ are distinct and belong to different connected components of the
graph $G^{*}\setminus e^{*}$. Therefore, every path in $G^{*}$ connecting
$f_{1}^{*}$ and $f_{2}^{*}$ should contain $e^{*}$. This, in turn, implies
that every arc of the surface whose endpoints are in the faces $f_{1}$ and
$f_{2}$ of $G$ and does not cross any vertices of $G$, should cross $e$. Thus,
$e$ together with its endpoints form a closed arc, implying that $e$ is a
loop, a contradiction. ∎

###  2.5 Proof of Theorem 1

Let $G$ be a connected loopless bridgeless graph embedded on a surface of
Euler genus $g$. Observe that $G^{*}$ is also connected and since $G$ is
loopless, $G^{*}$ is also bridgeless. By Proposition 2,
$\mathbf{bw}(G)=\mu\text{-}\mathbf{bw}(G)$ and
$\mathbf{bw}(G^{*})=\mu\text{-}\mathbf{bw}(G^{*})$. We consider a connected
branch decomposition of $G$ of width $\mu\text{-}\mathbf{bw}(G)$. This can be
done using Proposition 1.

Now, let $F\subseteq E(G)$ such that $G[F]$ and $G\setminus F$ are connected.
We inductively define a finite sequence of graphs $G_{0},G_{1},\ldots$
obtained as follows. First, we set $G_{0}:=G$ and $F_{0}:=F$. For every
integer $i\geq 1$, if there is an edge $e\in F_{i-1}$ such that $e$ is not a
loop in $G_{i-1}$ and its dual edge $e^{*}$ in $E(G_{i-1}^{*})$ is a bridge of
$G_{i-1}^{*}[F_{i-1}^{*}]$, we define $G_{i}:=G_{i-1}/e$ and
$F_{i}:=F_{i-1}^{/e}$. Observe that $G_{i}$ is bridgeless, connected, and
embedded on $M$, and both $G_{i}[F_{i}]$ and $G_{i}\setminus F_{i}$ are
connected. Note also that since $e$ is not a loop in $G_{i-1}$, $e^{*}$ is not
a bridge in $G_{i-1}^{*}$. Moreover, the fact that $e^{*}$ is a bridge of
$G_{i-1}^{*}[F_{i-1}^{*}]$ and Lemma 4 imply that
$e\subseteq\partial(F_{i-1})$. Therefore, by Lemma 2 and Lemma 3 it holds that

$|\mu_{G_{i-1}}(F_{i-1})-\mu_{G_{i-1}^{*}}(F_{i-1}^{*})|=|\mu_{G_{i}}(F_{i})-\mu_{G_{i}^{*}}(F_{i}^{*})|.$
(1)

Let $k\in\mathbb{N}$ such that for every edge $e\in F_{k}$ that is not a loop
in $G_{k}$, its dual edge $e^{*}$ is contained in some cycle of
$G_{k}^{*}[F_{k}^{*}]$. By (1), we have that

$|\mu_{G}(F)-\mu_{G^{*}}(F^{*})|=|\mu_{G_{k}}(F_{k})-\mu_{G_{k}^{*}}(F_{k}^{*})|.$

Now observe that if $G_{k}^{*}[F_{k}^{*}]$ has a cycle basis $\mathcal{C}$,
where $|\mathcal{C}|>g$, then by Lemma 5, there exists an edge $e\in F_{k}$
such that $e^{*}$ belongs to a cycle of $\mathcal{C}$ and $e$ is not a subset
of $\partial(F_{k})$. Therefore, by Lemma 2 and Lemma 3,
$\mu_{G_{k}}(F_{k})=\mu_{G_{k}/e}(F_{k}^{/e})$ and
$\mu_{G_{k}^{*}}(F_{k}^{*})=\mu_{G_{k}^{*}\setminus e^{*}}(F_{k}^{*}\setminus
e^{*})$. Also observe that the removal of $e^{*}$ from $G^{*}[F^{*}]$ reduces
the circuit rank of $G^{*}[F^{*}]$ by one. Applying iteratively the above
argument, we can obtain a graph $\tilde{G}$ and a set $\tilde{F}$ such that
$\tilde{G}$ is bridgeless, connected, and embedded on $M$,
$\tilde{G}[\tilde{F}]$ and $\tilde{G}\setminus\tilde{F}$ are connected,

$|\mu_{G}(F)-\mu_{G^{*}}(F^{*})|=|\mu_{\tilde{G}}(\tilde{F})-\mu_{\tilde{G}^{*}}(\tilde{F}^{*})|,$
(2)

and the circuit rank of $\tilde{G}^{*}[\tilde{F}^{*}]$ is at most $g$.

Now, notice that since Lemma 5 cannot be applied for the graph $\tilde{G}$ and
the set $\tilde{F}$, we not guaranteed the existence of a (non-loop) edge
whose dual is not a bridge of $\tilde{G}^{*}[\tilde{F}^{*}]$ and
$e\nsubseteq\partial(F)$. Thus, by contracting a non-loop edge $e\in\tilde{F}$
of $\tilde{G}$ whose dual is not a bridge of $\tilde{G}^{*}[\tilde{F}^{*}]$,
due to Lemma 2 and Lemma 3, we have that

$\mu_{\tilde{G}^{*}\setminus e^{*}}(\tilde{F}^{*}\setminus
e^{*})=\mu_{\tilde{G}^{*}}(\tilde{F}^{*})\mbox{~{}and~{}}\mu_{\tilde{G}/e}(\tilde{F}^{/e})=\begin{cases}\mu_{\tilde{G}}(\tilde{F})-1,&\text{
if $e\subseteq\partial(F)$ and}\\\ \mu_{\tilde{G}}(\tilde{F}),&\text{
otherwise}.\end{cases}$

Note also that the removal of $e^{*}$ from $\tilde{G}^{*}[\tilde{F}^{*}]$
reduces the circuit rank of $\tilde{G}^{*}[\tilde{F}^{*}]$ by one. Therefore,
after iteratively contracting non-loop edges in the set $\tilde{F}$, we obtain
a connected (bridgeless) graph $\hat{G}$ embedded on $M$ and a set
$\hat{F}\subseteq E(\hat{G})$ such that $\hat{G}[\hat{F}]$ is a single-vertex
graph (whose edges are all loops), $\hat{G}\setminus\hat{F}$ is connected, and

$\mu_{\hat{G}^{*}}(\hat{F}^{*})=\mu_{\tilde{G}^{*}}(\tilde{F}^{*})\mbox{~{}and~{}}\mu_{\tilde{G}}(\tilde{F})-r\leq\mu_{\hat{G}}(\hat{F})\leq\mu_{\tilde{G}}(\tilde{F}),$
(3)

for some $r\in\mathbb{N}$ such that $r\leq g$. Moreover, keep in mind that $r$
corresponds to the number of contracted non-loop edges in this step and
therefore if $c$ is the circuit rank of $\hat{G}^{*}[\hat{F}^{*}]$, then
$c+r\leq g$.

Observe now that since $\hat{G}^{*}[\hat{F}^{*}]$ has circuit rank $c\leq g$,
by Lemma 1 the contraction of the dual edge $e^{*}$ of a loop $e\in\hat{F}$
may reduce $\mu_{\hat{G}^{*}}(\hat{F}^{*})$ by one. Also, by Lemma 3, the
removal of a loop in $\hat{F}$ (being a loop implies that it is neither a
bridge of $\hat{G}$ nor of $\hat{G}[\hat{F}]$) does not reduce
$\mu_{\hat{G}}(\hat{F})$. Therefore, removing all remaining (loop) edges in
$\hat{F}$, we obtain the graph $\breve{G}$ that is either empty, or connected
and embedded in $M$, such that

$\mu_{\hat{G}^{*}}(\hat{F}^{*})-\ell\leq\mu_{\breve{G}^{*}}(\emptyset)\leq\mu_{\hat{G}^{*}}(\hat{F}^{*})\text{~{}and~{}}\mu_{\breve{G}}(\emptyset)=\mu_{\hat{G}}(\hat{F})$
(4)

for some $\ell\in\mathbb{N}$ such that $\ell\leq c$. Since $c+r\leq g$, we
have that $\ell+r\leq g$, which also implies that $|\ell-r|\leq g$. By
combining (3) and (4), we obtain

$\mu_{\tilde{G}^{*}}(\tilde{F}^{*})-\ell\leq\mu_{\breve{G}^{*}}(\emptyset)\leq\mu_{\tilde{G}^{*}}(\tilde{F}^{*})\text{~{}and~{}}\mu_{\tilde{G}}(\tilde{F})-r\leq\mu_{\breve{G}}(\emptyset)\leq\mu_{\tilde{G}}(\tilde{F}),$

which in turn implies that

$\big{|}|\mu_{\tilde{G}}(\tilde{F})-\mu_{\tilde{G}^{*}}(\tilde{F}^{*})|-r+\ell\big{|}\leq|\mu_{\breve{G}}(\emptyset)-\mu_{\breve{G}^{*}}(\emptyset)|.$

This, together with the fact that
$\mu_{\breve{G}}(\emptyset)=\mu_{\breve{G}^{*}}(\emptyset)=1$, implies that
$|\mu_{\tilde{G}}(\tilde{F})-\mu_{\tilde{G}^{*}}(\tilde{F}^{*})|\leq|\ell-r|\leq
g.$ Moreover, using (2), we get

$|\mu_{G}(F)-\mu_{G^{*}}(F^{*})|\leq g.$

Consider now a branch decomposition $(T,\lambda)$ of $G$ and its dual
$(T,\lambda^{*})$. If $w_{\mu}(T,\lambda^{\prime})=\mu_{G^{*}}(F^{*})$ for
some $F\subseteq E(G)$, then
$w_{\mu}(T,\lambda^{\prime})=\mu_{G^{*}}(F^{*})\leq\mu_{G}(F)+g\leq
w_{\mu}(T,\lambda)+g$. Hence, if $(T,\lambda)$ is an optimal branch
decomposition for $G$, then $\mu\text{-}\mathbf{bw}(G)=w_{\mu}(T,\lambda)\geq
w_{\mu}(T,\lambda^{\prime})-g\geq\mu\text{-}\mathbf{bw}(G^{*})-g$. This,
together with the fact that $\mu\text{-}\mathbf{bw}(G)=\mathbf{bw}(G)$ and
$\mu\text{-}\mathbf{bw}(G^{*})=\mathbf{bw}(G^{*})$, implies that
$\mathbf{bw}(G^{*})\leq\mathbf{bw}(G)+g$.

##  3 From graphs to hypergraphs

Before we proceed to the proof of Theorem 2 we need to establish some more
notation.

###  3.1 Incidence graphs and their branch decompositions

In this subsection we show how to obtain a branch decomposition of the
incidence graph of a hypergraph from a branch decomposition of the hypergraph.
Then, we prove that the branchwidth of a hypergraph and its _incidence graph_
are the same (Lemma 7) and the same holds after taking the dual (Lemma 8).

#### Incidence graphs.

For a given hypergraph $G$ we define its _incidence graph_ , which we denote
by $I(G)$, the graph whose vertex set is $V(G)\cup E(G)$ and two vertices of
$I(G)$ are adjacent if and only if one is associated with a vertex $v$ of $G$,
the other is associated with a hyperedge $h$ of $G$, and $v$ is an endpoint of
$h$.

Given a vertex $v_{h}$ of $I(G)$ associated with the hyperedge $h$ of $G$, we
use $E_{I}(h)$ to denote the set of edges of $I(G)$ that are incident to
$v_{h}$. Observe that for every edge $e$ of $I(G)$ there is a unique hyperedge
$h\in E(G)$ such that $e\in E_{I}(h)$. Therefore, $\\{E_{I}(h)\mid h\in
E(G)\\}$ is a partition of $E(I(G))$.

#### Embedding incidence graphs.

Let $G$ be a hypergraph embedded on a surface $\Sigma$. Notice that any given
embedding of $G$ on $\Sigma$ naturally defines an embedding of $I(G)$ on
$\Sigma$. The vertices of $I(G)$ that are associated with vertices of $G$ are
represented as the respective vertices of $G$, the vertices of $I(G)$ that are
associated with hyperedges of $G$ are represented as the centres of the
respective stars of $G$. An edge $\\{v_{x},v_{e}\\}$ of $I(G)$, where $v_{x}$
is the vertex of $I(G)$ that is associated with the vertex $x$ of $G$ and
$v_{e}$ is the vertex of $I(G)$ that is associated with the hyperedge $e$ of
$G$, is represented as the half edge that connects $x$ with the centre of $e$.
Given an embedding of $G$ on some surface $\Sigma$, we will always embed
$I(G)$ on $\Sigma$ as above and we will make no distinction between the edges
of $I(G)$ and the half-edges of $G$ to which the corresponding edges of $I(G)$
are associated.

#### Branch decompositions of incidence graphs.

Let $(T,\lambda)$ be a branch decomposition of a hypergraph $G$. We will
denote by $(\mathsf{Inc}(T),\mathsf{Inc}(\lambda))$ a branch decomposition of
$I(G)$ that is obtained from $T$ as follows: first, for each edge $e$ of $G$,
we construct a binary tree $T_{e}$ and we set $\lambda_{e}$ to be a bijection
from $L(T_{e})$ to $E_{I}(e)$. We call such a tree a _half-edge tree_. Keep in
mind that for every edge $e\in E(G)$, one can define many different trees
$T_{e}$ and bijections $\lambda_{e}$ from $L(T_{e})$ to $E_{I}(e)$. For each
$e\in E(G)$, consider a pair $(T_{e},\lambda_{e})$. Then, pick an edge
$\\{u,v\\}$ of $T_{e}$, remove it, add a new vertex $z_{e}$, and make $z_{e}$
adjacent to $u$ and $v$. We denote this tree by $\tilde{T}_{e}$. We now define
$\mathsf{Inc}(T)$ to be the tree obtained from $T$ after taking the disjoint
union of $T$ and $\bigcup_{t\in L(T)}\tilde{T}_{\lambda(t)}$ and, for every
$t\in L(T)$, identifying $t$ with $z_{\lambda(t)}$. Also, we set
$\mathsf{Inc}(\lambda)$ be the disjoint union of the bijections
$\lambda_{e},e\in E(G)$, i.e., for every $t\in L(\mathsf{Inc}(T))$, if $t\in
L(T_{e})$ for some $e\in E(G)$, then $\mathsf{Inc}(\lambda)$ maps $t$ to
$\lambda_{e}(t)$.

To prove Theorem 2 we first show the following intermediate results.

######  Lemma 7.

Let $(T,\lambda)$ be a branch decomposition of a hypergraph $G$. Then
$w_{\delta}(T,\lambda)=w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda))$.

###### Proof.

Recall that by definition, the edges of $\mathsf{Inc}(T)$ are partitioned to
the set $E(T)$ and the edge sets of the half-edge trees $E(T_{h})$, for all
$h\in E(G)$. Let $e$ be an edge of $\mathsf{Inc}(T)$. There is an
$F\subseteq\bigcup_{h\in E(G)}E_{I}(h)$ such that
$\delta_{\mathsf{Inc}(\lambda)}(e)=|\partial(F)|$. We distinguish cases,
depending whether $e\in E(T)$ or $e\in E(T_{h})$, for some $h\in E(G)$.

If $e\in E(T)$, then notice that if for some hyperedge $y\in E(G)$ we have
$x\in E_{I}(y)$ and $x\in F$ then $E_{I}(y)\subseteq F$ and if $x\notin F$,
then then $E_{I}(y)\cap F=\emptyset$. Therefore, there is a set $D\subseteq
E(G)$ such that $F=\bigcup_{h\in D}E_{I}(h)$. Observe that the union of the
closure of all arcs in $F$ and the union of the closure of all arcs in $D$
define the same subsets of $\Sigma$. Hence,
$\delta_{\mathsf{Inc}(\lambda)}(e)=|\partial(F)|=|\partial(D)|=\delta_{\lambda}(e)$.

If $e$ belongs to $T_{h}$ for some $h\in E(G)$, then $F\subseteq E_{I}(h)$.
Moreover, notice that $\partial(F)$ is equal to a proper subset of the set of
endpoints of the edges in $E_{I}(h)$ that contains the common endpoint of all
edges in $E_{I}(h)$ (intuitively, the center of a star together with some of
its degree-one vertices). Therefore,
$\delta_{\mathsf{Inc}(\lambda)}(e)=|\partial(F)|<|\partial(E_{I}(h))|=\delta_{\mathsf{Inc}(\lambda)}(e^{\prime})$
for $e^{\prime}$ being the edge of $\mathsf{Inc}(T)$ in $E(T)$ that is
incident to the root of $T_{h}$.

Thus, $w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda))$ is obtained for a
partition of $E(I(G))$ defined by an edge $e\in E(T)$, and in this case
$\delta_{\mathsf{Inc}(\lambda)}(e)=\delta_{\lambda}(e)$. ∎

######  Lemma 8.

Let $(T,\lambda)$ be a branch decomposition of a hypergraph $G$ and let
$(T,\lambda^{*})$ be its dual branch decomposition. Then
$w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda)^{*})=w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda^{*}))$.

###### Proof.

We will show that
$w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda)^{*})=\delta_{\mathsf{Inc}(\lambda)^{*}}(e)$
for some $e\in E(T)$. This will imply that
$w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda)^{*})=w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda^{*}))$.

We observe that, for a star $h$ of $G$, $E_{I}(h)^{*}$ is a cycle of
$I(G)^{*}$ with as many edges as $E_{I}(h)$. Let $e$ be an edge of
$\mathsf{Inc}(T)$ that belongs to a subtree $T_{h}$, for some $h\in E(G)$.
Then $\delta_{\mathsf{Inc}(\lambda)^{*}}(e)=|\partial(F)|$, wherein
$F\subseteq E(h)^{*}$. Thus,
$|\partial(F)|\leq\delta_{\mathsf{Inc}(\lambda)^{*}}(e^{\prime})$, wherein
$e^{\prime}$ is the edge of $\mathsf{Inc}(T)$ that is in $E(T)$ and is
incident to the root of $T_{h}$.

We will show that for every $e\in T$,
$\delta_{\mathsf{Inc}(\lambda^{*})}(e)=\delta_{\mathsf{Inc}(\lambda)^{*}}(e)$.
First let $F\subseteq E(I(G^{*}))$ such that
$\delta_{\mathsf{Inc}(\lambda^{*})}(e)=|\partial(F^{*})|$. Let also
$F^{\prime}\subseteq E(I(G)^{*})$ such that
$\delta_{\mathsf{Inc}(\lambda)^{*}}(e)=|\partial(F^{\prime})|$. We will prove
that $\partial(F)=\partial(F^{\prime})$. The fact that $e\in T$ implies that
there is some $D\subseteq E(G^{*})$ and some $D^{\prime}\subseteq E(G)$ such
that

$F=\bigcup_{h^{*}\in D}\\{z\mid z\in
E_{I}(h^{*})\\}\text{~{}and~{}}F^{\prime}=\bigcup_{h\in
D^{\prime}}\\{z^{*}\mid z\in E_{I}(h)\\}.$

Note that $D^{*}=D^{\prime}$ and therefore, for every $h^{*}\in D$, since the
endpoints of the star (in $I(G^{*})$) corresponding to $h^{*}$ are the same as
the endpoints of the duals of the edges of the star (in $I(G)$) corresponding
to $h$, i.e., $\bigcup_{z\in E_{I}(h^{*})}z=\bigcup_{z\in E_{I}(h)}z^{*}$.
Therefore, $\partial(F)\cap\bigcup_{z\in
E_{I}(h^{*})}z=\partial(F^{\prime})\cap\bigcup_{z\in E_{I}(h)}z^{*}$, which in
turn implies that $\partial(F)=\partial(F^{\prime})$. Hence,
$\delta_{\mathsf{Inc}(\lambda^{*})}(e)=\delta_{\mathsf{Inc}(\lambda)^{*}}(e)$.
∎

###  3.2 Proof of Theorem 2

Let an optimal branch decomposition of a hypergraph $G$, say $(T,\lambda)$,
such that $\mathbf{bw}(G)=w_{\delta}(T,\lambda)$. Therefore, using Lemma 7, we
derive that
$\mathbf{bw}(G)=w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda))$. Observe
that by applying Theorem 1 to $I(G)$, we have that
$w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda))\geq
w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda)^{*})-\mathbf{eg}(G)$.
Therefore, it holds that $\mathbf{bw}(G)\geq
w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda)^{*})-\mathbf{eg}(G)$.
Following Lemma 8, we get that

$\mathbf{bw}(G)\geq
w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda^{*}))-\mathbf{eg}(G).$

This together with the fact that
$w_{\delta}(\mathsf{Inc}(T),\mathsf{Inc}(\lambda^{*}))\geq\mathbf{bw}(G^{*})$
implies that $\mathbf{bw}(G^{*})\leq\mathbf{bw}(G)+\mathbf{eg}(G)$.

#### Acknowledgements.

We are all thankful to Dimitrios M. Thilikos for communicating us the problem
and inviting us to write its proof. The valuable guidance, inspiration, and
knowledge that he generously offered, helped us in many different stages of
this project.

## References

  * [1] Omid Amini, Florian Huc, and Stéphane Pérennes.  On the path-width of planar graphs.  SIAM Journal on Discrete Mathematics, 23(3):1311–1316, 2009.
  * [2] Lali Barrière, Paola Flocchini, Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse, Nicola Santoro, and Dimitrios M. Thilikos.  Connected graph searching.  Information and Computation, 219:1–16, 2012.
  * [3] Hans L. Bodlaender and Fedor V. Fomin.  Approximation of pathwidth of outerplanar graphs.  Journal of Algorithms, 43(2):190–200, 2002.
  * [4] Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca.  Chordal embeddings of planar graphs.  Discrete Mathematics, 273(1):85–102, 2003.
  * [5] Fedor V. Fomin and Dimitrios M. Thilikos.  On self duality of pathwidth in polyhedral graph embeddings.  Journal of Graph Theory, 55(1):42–54, 2007.
  * [6] James F. Geelen, Albertus M. H. Gerards, and Geoff Whittle.  Branch-width and well-quasi-ordering in matroids and graphs.  Journal of Combinatorial Theory, Series B, 84(2):270–290, 2002\.
  * [7] Illya V. Hicks and Nolan B. McMurray.  The branchwidth of graphs and their cycle matroids.  Journal of Combinatorial Theory, Series B, 97(5):681–692, 2007\.
  * [8] Navin Kashyap.  Matroid pathwidth and code trellis complexity.  SIAM Journal on Discrete Mathematics, 22(1):256–272, 2008.
  * [9] Athanassios Koutsonas, Dimitrios M. Thilikos, and Koichi Yamazaki.  Outerplanar obstructions for matroid pathwidth.  Discrete Mathematics, 315-316:95–101, 2014.
  * [10] Denis Lapoire.  Treewidth and duality for planar hypergraphs, 1996.  Manuscript.
  * [11] Frédéric Mazoit.  Décomposition algorithmique des graphes.  PhD thesis, École Normale Supérieure de Lyon, 2004.
  * [12] Frédéric Mazoit.  Tree-width of graphs and surface duality.  Journal of Combinatorial Theory, Series B, 102(3):671–687, 2012\.
  * [13] Frédéric Mazoit and Stéphan Thomassé.  Branchwidth of graphic matroids.  In Surveys in Combinatorics 2007, volume 346 of London Mathematical Society Lecture Note Series, pages 275–286. Cambridge University Press, 2007.
  * [14] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces.  John Hopkins University Press, 2001.
  * [15] James Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [16] Neil Robertson and Paul D. Seymour.  Graph minors. III. Planar tree-width.  Journal of Combinatorial Theory, Series B, 36:49–64, 1984.
  * [17] Neil Robertson and Paul D. Seymour.  Graph minors. X. Obstructions to tree-decomposition.  Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991\.
  * [18] Neil Robertson and Paul D. Seymour.  Graph minors. XX. Wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.  Special Issue Dedicated to Professor W.T. Tutte.
  * [19] Ignasi Sau and Dimitrios M. Thilikos.  On self-duality of branchwidth in graphs of bounded genus.  Discrete Applied Mathematics, 159(17):2184–2186, 2011.
  * [20] Paul D. Seymour and Robin Thomas.  Call routing and the ratcatcher.  Combinatorica, 14(2):217–241, 1994.
  * [21] Martin Vatshelle.  New Width Parameters of Graphs.  PhD thesis, University of Bergen, 2012.