# Outerplanar obstructions for matroid pathwidth

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

► To cite this version:

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki. Outerplanar obstructions for matroid pathwidth. Discrete Mathematics, 2013, 315-316, pp.95-101. 10.1016/j.disc.2013.10.007. lirmm-01083516

HAL Id: lirmm-01083516

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083516

Submitted on 17 Nov 2014

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Outerplanar Obstructions for Matroid Pathwidth

Athanassios Koutsonas<sup>a,1</sup>, Dimitrios M. Thilikos<sup>a,b,2</sup>, Koichi Yamazaki<sup>c</sup>

<sup>a</sup>Department of Mathematics, National and Kapodistrian University of Athens,
Panepistimioupolis, GR-15784 Athens, Greece

<sup>b</sup>AlGCo project-team, CNRS, LIRMM, France

<sup>c</sup>Department of Computer Science
Faculty of Engineering, Gunma University

Gunma, Japan

## Abstract

For each non-negative integer $k$, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most $k$. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth.

*Keywords:* matroids, obstructions, pathwidth, outerplanar graphs.

## 1. Introduction

The notions of pathwidth and branchwidth are fundamental graph pa- rameters that appear in many topics of discrete mathematics and algorithms. The counterpart of branchwidth on matroids has been introduced by Geelen and Whittle in [6] and was extensively studied in [1, 5, 8, 13, 10]. How- ever, not much is known for the counterpart of this parameter on matroids. The pathwidth of a matroid was defined by Geelen, Gerards, and Whittle

Email addresses: akoutson@math.uoa.gr (Athanassios Koutsonas), sedthilk@thilikos.info (Dimitrios M. Thilikos), koichi@cs.gunma-u.ac.jp (Koichi Yamazaki)

<footnote n="1"><sup>1</sup>Supported by the project "Support of Research" of the National and Kapodistrian University of Athens (project code: 10812).</footnote>

<footnote n="2"><sup>2</sup>Co-financed by the European Union (European Social Fund – ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) - Research Funding Program: "Thalis. Investing in knowledge society through the European Social Fund".</footnote>
in [7] (see also [9]) and was extensively studied in the work of Kashyap [13]
in the context of trellis state-complexity of linear codes. Also, connected
matroids of pathwidth at most 3 have been studied in [8, 1].

Given a class of matroids $\mathcal{M}$, we define its obstruction set $\mathbf{obs}(\mathcal{M})$ as
the set of all minor-minimal matroids not in $\mathcal{M}$ (similarly, we define $\mathbf{obs}(\mathcal{G})$
for the case where $\mathcal{G}$ is a class of graphs). We define $\mathcal{P}_k$ as the class of all
matroids of pathwidth at most $k$. In this paper, we study the set $\mathbf{obs}(\mathcal{P}_k)$
and we characterize, for every $k$, all members of $\mathbf{obs}(\mathcal{P}_k)$ that are cycle
matroids of outerplanar graphs.

Following Kashyap [13], we define the matroid-pathwidth (in short: $\mu$-pathwidth) of a graph as the pathwidth of its cycle matroid. As observed in [13], the pathwidth and the $\mu$-pathwidth of a graph are different parameters, while the pathwidth can be computationally reduced to $\mu$-pathwidth.

In this paper we show that several structural characteristics of the path-
width of acyclic graphs are transferred to the $\mu$-pathwidth of outerplanar
graphs. In particular, we define an operation, called *fusion* for “joining
together” triples of matroids and we prove a structural result (Lemma 3)
that provides a way to construct matroids of pathwid at least $k + 1$ from
matroids of pathwidth at least $k$. Our result can be seen as the matroid-
analogue of the operation defined in [19] (see also [20, 17, 3]) for the case
of the pathwid of graphs (see also [12] for related recent results for the
parameter of linear rank-width).

Using our structural lemma, we prove the existence of a bijection between
acyclic obstructions for linear-width (a parameter very similar to the path-
width for graphs) and the outerplanar obstructions of $\mu$-pathwidth. This
gives a precise characterization of all members of $\mathbf{obs}(\mathcal{P}_k)$ that are cycle
matroids of outerplanar graphs. A byproduct of our results is that the $\mu$-
pathwidth of outerplanar graphs can be computed in linear time.

## 2. Definitions and Preliminaries

Given a graph $G$, we denote by $V(G)$ its vertex set and as $E(G)$ its edge
set. We consider graphs that may have loops or multiple edges. If a graph
has no multiple edges or loops we call it *simple*. For any set of vertices
$S \subseteq V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by the vertices in
$S$. Accordingly, for a set of edges $F \subseteq E(G)$, we define $G[F] = (V(F), F)$
where $V(F) = \bigcup_{e \in F} e$. In addition, we define by $\bar{F} = E(G) - F$.

We use the term *plane graph* for a planar graph along with an embed-
ding of it in the sphere $S_0$ without crossings. To simplify notations, we do
not distinguish between a vertex of the graph and the point of $S_0$ used in
the drawing to represent the vertex or between an edge and the open line segment representing it. We denote by $F(G)$, the set of faces of this embedding, i.e. the connected components of $S_0 \setminus G$, (that are open sets of $S_0$). A planar graph $G$ is outerplanar if it has an embedding on the sphere $S_0$ such that all its vertices lie on the boundary of a single face, called outer face.

Given two graphs $H$ and $G$, we write $H \preceq G$ and call $H$ a minor of $G$, if $H$ can be obtained by a subgraph of $G$ after a series of edge contractions. We also use the notation $G^*$ to denote an embedding of the dual graph of $G$.

**Matroids and cycle matroids of graphs.** Given a matroid $\mathcal{M}$, we use the notations $E(\mathcal{M})$ and $\mathcal{I}(\mathcal{M})$ for its elements and the collection of its independent sets respectively. We also call $E(\mathcal{M})$ the ground set of $\mathcal{M}$. Moreover, following the notation of [16], we denote by $\mathcal{B}(\mathcal{M})$ the collection of the maximal independent sets, the bases of $\mathcal{M}$ and $\mathcal{C}(\mathcal{M})$ the collection of the minimal dependent sets, the circuits of $\mathcal{M}$. It is known (see e.g., [16]) that any of the collections $\mathcal{I}(\mathcal{M})$, $\mathcal{B}(\mathcal{M})$ or $\mathcal{C}(\mathcal{M})$ suffices to describe a matroid $\mathcal{M}$ on an element set $E(\mathcal{M})$.

The cycle matroid of a graph $G$, denoted as $\mathcal{M}(G)$, has $E(G)$ as ground set, while its independent sets are the sub-forests of $G$. On the other hand, a matroid that is isomorphic to a cycle matroid of a graph is called *graphic*.

Given a matroid $\mathcal{M}$, the matroid whose ground set is $E(\mathcal{M})$ and whose collection of bases is $\{E(\mathcal{M}) - B : B \in \mathcal{B}(\mathcal{M})\}$ is called the *dual* of the matroid $\mathcal{M}$ and is denoted by $\mathcal{M}^*$.

Let $\mathcal{M}$ be a matroid and $X, Y \subseteq E(\mathcal{M})$ subsets of its ground set. The matroid $\mathcal{M} \setminus X = \{E(\mathcal{M}) - X, I \subseteq (E(\mathcal{M}) - X) : I \in \mathcal{I}(\mathcal{M})\}$ and the matroid $\mathcal{M}/Y = [\mathcal{M}^* \setminus Y]^*$ are the *deletion* of $X$ and the *contraction* of $Y$ from the matroid $\mathcal{M}$, respectively. If $X = \{e\}$ then we simply write $\mathcal{M} \setminus e$ instead of $\mathcal{M} \setminus \{e\}$ – likewise for the contraction of a single element. A matroid $\mathcal{K}$ is a minor of a matroid $\mathcal{M}$ if $K = \mathcal{M} \setminus X/Y$ for some $X, Y \subseteq E(\mathcal{M})$.

The *matroid connectivity function* $\lambda: 2^{E(\mathcal{M})} \to \mathbb{N}$ is defined as follows:

$$ \lambda_{\mathcal{M}}(X) = r_{\mathcal{M}}(X) + r_{\mathcal{M}}(\bar{X}) - r_{\mathcal{M}}(E(\mathcal{M})) $$

where $\bar{X} = E(\mathcal{M}) - X$ and $r$ is the rank function of $\mathcal{M}$, i.e. $r_{\mathcal{M}}(X)$ is the maximum cardinality of an independent set of $X$ in $\mathcal{M}$.

A matroid that for every pair of distinct elements of its ground set has a circuit containing both of them is called *connected*. This implies that the cycle matroid of a 2-connected graph is connected. It is also easy to check that if a matroid $\mathcal{M}$ is connected and $F \subseteq E(\mathcal{M})$, then $\lambda_{\mathcal{M}}(F) = 0$ only if $F = E(\mathcal{M})$ or $F = \emptyset$.
Another useful property of connectivity is the following:

**Fact 1 ([22]).** Let $e$ be an element of a connected matroid $\mathcal{M}$. Then at least one of $\mathcal{M}/e$ and $\mathcal{M}\setminus e$ is connected.

Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ on disjoint ground sets, we denote by $\mathcal{M}_1 \oplus \mathcal{M}_2$ their direct sum, i.e. the matroid $(E(\mathcal{M}_1) \cup E(\mathcal{M}_2), \mathcal{I}(\mathcal{M}_1) \cup \mathcal{I}(\mathcal{M}_2))$.

We continue with the definition of two dual operations on matroids which will play an important role in the proofs of the next section. If an element is not contained in a base of a matroid, then it is called loop, while if it is in every base is called coloop. Then, given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ with $E(\mathcal{M}_1) \cap E(\mathcal{M}_2) = \{e\}$ where $e$ is neither a loop or a coloop in these matroids, the series connection of $\mathcal{M}_1$ and $\mathcal{M}_2$, denoted by $S(\mathcal{M}_1, \mathcal{M}_2)$, is the matroid with element set $E(\mathcal{M}_1 \setminus e) \cup E(\mathcal{M}_2 \setminus e) \cup e'$, where $e'$ is an element not in $E(\mathcal{M}_1)$ or $E(\mathcal{M}_2)$ and whose collection of circuits is:

$$ \mathcal{C}_S = \mathcal{C}(\mathcal{M}_1 \setminus e) \cup \mathcal{C}(\mathcal{M}_2 \setminus e) \cup \{(C_1 - e) \cup (C_2 - e) \cup e' : e \in C_i \in \mathcal{C}(\mathcal{M}_i) \text{ for } i = 1, 2\}. $$

Subsequently, the parallel connection of $\mathcal{M}_1$ and $\mathcal{M}_2$ denoted by $P(\mathcal{M}_1, \mathcal{M}_2)$ is the matroid $[S(\mathcal{M}_1^*, \mathcal{M}_2^*)]^*$. Properties of series and parallel connection include many attractive features. As example the classes of graphic matroids and connected matroids are closed under these operations – for a further study see also [16]. We will need the following property from [2]:

**Fact 2.** Let $\mathcal{N}_1, \mathcal{N}_2$ be two matroids where $E(\mathcal{N}_1) \cap E(\mathcal{N}_2) = \{e\}$. Then, $P(\mathcal{N}_1, \mathcal{N}_2)/e = (\mathcal{N}_1/e) \oplus (\mathcal{N}_2/e)$.

**Matroid Pathwidth.** Given a layout $L = (e_1, \dots, e_m)$ of $E(\mathcal{M})$, we define

$$ \mu\text{-width}_{\mathcal{M}}(L) = \max\{\lambda_{\mathcal{M}}(\{e_1, \dots, e_i\}) \mid 1 \le i \le m-1\}. $$

According to the definition of [7] the *pathwidth* of a matroid $\mathcal{M}$, denoted by $\mathbf{pw}(\mathcal{M})$, is the minimum $k$ for which there exists a layout $L = (e_1, \dots, e_m)$ of its elements such that $\mu\text{-width}_{\mathcal{M}}(L) \le k$.

The matroid pathwidth of a graph $G$ (or simply $\mu$-pathwidth) is defined as the pathwidth of its cycle matroid and it is denoted as $\mu\text{-pw}(G)$, in other words:

$$ \mu\text{-pw}(G) = \mathbf{pw}(\mathcal{M}(G)). $$

We will need the following simple lemma:
**Lemma 1.** The $\mu$-pathwidth of a graph is equal to the maximum $\mu$-pathwidth of all its biconnected components.

**Proof.** Let {$C_1, \dots, C_r$} be the biconnected components of a graph $G$ and $E_1, \dots, E_r$ the corresponding edge sets. Then, for $i = 1, \dots, r$ it holds that $r_M(E_i) + r_M(\bar{E}_i) = r(M)$, where by $M$ is denoted the cycle matroid of $G$. This implies that the value of the connectivity function of a set of edges belonging to the same component, is irrelevant from the rest of the biconnected components. This implies that if $\mu$-width($L_i$) $\le k$ for $i = 1, \dots, r$, where $L_i$ is a layout of $E_i$, then for the concatenation $L$ of all these layouts it also holds $\mu$-width($L$) $\le k$. $\square$

### 3. A Decomposition of Matroids

Let $M_1, M_2, M_3$ be connected matroids on disjoint edge sets and for each of them pick an element $e_i \in E(M_i)$, $i = 1, 2, 3$. The uniform matroid $U_{1,3}$ with elements {$e_1, e_2, e_3$} shares one common element with each of the three matroids: $E(U_{1,3}) \cap E(M_i) = \{e_i\}$. We call fusion of $M_1, M_2, M_3$ on the elements {$e_1, e_2, e_3$} the matroid

$$M = S(S(S(U_{1,3}, M_1), M_2), M_3)$$

and we denote it by fusion($M_1, M_2, M_3, e_1, e_2, e_3$). It is easy to check that this matroid is also connected. The elements $e_1, e_2, e_3$ on which the fusion takes place will be referred to as bridge elements.

The series connections in the definition of $M$ involve the three elements of $U_{1,3}$ which implies that the order in which the connections are performed is irrelevant. Consider now the matroid $S(S(U_{1,3}, M_1), M_2)$ one step before the composition of the final matroid $M$. Let $M^{(1)}$ and $M^{(2)}$ be matroids isomorphic to $U_{1,2}$ where $E(M^{(1)}) = \{e_1, e_3\}$ and $E(M^{(2)}) = \{e_2, e_3\}$. Keeping in mind that $U_{1,3}$ is isomorphic to $P(M^{(1)}, M^{(2)})$ we can observe the following:

**Observation 1.** The matroid $P(S(M^{(1)}, M_1), S(M^{(2)}, M_2))$ is isomorphic to the matroid $S(S(U_{1,3}, M_1), M_2)$.

In order to estimate the pathwidth of the fusion of three given matroids we need the following lemma about the connectivity function of a matroid formed by a series connection:
**Lemma 2.** Let $\mathcal{M}_1, \mathcal{M}_2$ be connected matroids with $E(\mathcal{M}_1) \cap E(\mathcal{M}_2) = \{e\}$ and $\mathcal{M} = S(\mathcal{M}_1, \mathcal{M}_2)$. For any two sets $F_1, F_2$ where $F_1 \subseteq E(\mathcal{M}_1)$ and $F_2 \subseteq E(\mathcal{M}_2 \setminus e)$ it holds that

$$ \lambda_M(F_1 \cup F_2) \geq \lambda_{\mathcal{M}_1}(F_1) + \lambda_{\mathcal{M}_2 \setminus e}(F_2) $$

**Proof.** Let $\mathcal{M}_i^- = \mathcal{M}_i \setminus e$, $i = 1, 2$. Since $\mathcal{M}_1, \mathcal{M}_2$ are both connected matroids it follows that their series connection $\mathcal{M}$ is also connected. From the connectivity of $\mathcal{M}_i$, we obtain that $r(\mathcal{M}_i) = r(\mathcal{M}_i^-)$, $i = 1, 2$. Also, from the connectivity of $\mathcal{M}$ it follows that $r(\mathcal{M}) = r(\mathcal{M} \setminus e)$. Notice that $\mathcal{M} = S(\mathcal{M}_1, \mathcal{M}_2)$ implies that $\mathcal{M} \setminus e = \mathcal{M}_1^- \oplus \mathcal{M}_2^-$, which, in turn, implies that $r(\mathcal{M}) = r(\mathcal{M}_1) + r(\mathcal{M}_2^-)$. From the definition of the connectivity function $\lambda$ and the last equality, it is enough to prove that for any two subsets $F_1 \subseteq E(\mathcal{M}_1), F_2 \subseteq E(\mathcal{M}_2^-)$,

$$ r_M(F_1 \cup F_2) \geq r_{\mathcal{M}_1}(F_1) + r_{\mathcal{M}_2^-}(F_2) \quad (1) $$

$$ r_M(\overline{F_1 \cup F_2}) \geq r_{\mathcal{M}_1}(\overline{F_1}) + r_{\mathcal{M}_2^-}(\overline{F_2}) \quad (2) $$

Towards a contradiction, suppose that $r_M(F_1 \cup F_2) < r_{\mathcal{M}_1}(F_1) + r_{\mathcal{M}_2^-}(F_2)$ and let $B_1, B_2$ be bases of $F_1, F_2$ respectively. Then $B_1 \cup B_2$ should contain a circuit $C$ in $\mathcal{M}$. Moreover, since $B_1 \cap B_2 = \emptyset$ the circuit $C$ has elements from both $B_1, B_2$ – as otherwise it would contradict their choice as bases. Contracting the elements of $\mathcal{M}_2^-$ in $\mathcal{M}$ will force the existence of a circuit $C_1 \subseteq C \cap E(\mathcal{M}_1) = B_1$ in $M/E(\mathcal{M}_2^-) = \mathcal{M}_1$ which contradicts that $B_1$ is a base in $\mathcal{M}_1$ and completes the proof of (1). Then (2) easily follows from (1) by the symmetry of the connectivity function $\lambda$ and the fact that $\overline{F_1} \cup \overline{F_2} = \overline{F_1} \cup \overline{F_2}$ (recall that $F_1 \cap F_2 = \emptyset$). $\square$

We are now ready to prove the main structural result of this paper.

**Lemma 3.** Let $\mathcal{M}$ be a matroid that is obtained by the fusion of three connected matroids $\mathcal{M}_a, \mathcal{M}_b, \mathcal{M}_c$. Then it holds that

$$ \mathrm{pw}(\mathcal{M}) \geq \min\{\mathrm{pw}(\mathcal{M}_a), \mathrm{pw}(\mathcal{M}_b), \mathrm{pw}(\mathcal{M}_c)\} + 1. $$

**Proof.** We will prove that, for any layout $L = (e_1, \dots, e_m)$ of the element set $E(\mathcal{M})$ of $\mathcal{M}$, there is an $q \in \{1, \dots, m-1\}$ such that $\lambda_{\mathcal{M}}(\{e_1, \dots, e_q\}) \geq k+1$ where $k = \min\{\mathrm{pw}(\mathcal{M}_a), \mathrm{pw}(\mathcal{M}_b), \mathrm{pw}(\mathcal{M}_c)\}$.

We denote by $e_a, e_b, e_c \in E(\mathcal{M})$ the bridge elements of the fusion associated with the matroids $\mathcal{M}_a, \mathcal{M}_b, \mathcal{M}_c$ respectively and, for simplicity, we use the notation $E_a = E(\mathcal{M}_a)$, $E_b = E(\mathcal{M}_b)$ and $E_c = E(\mathcal{M}_c)$. Assume
w.l.o.g. that $e_1 \in E_a$. Likewise, we assume that the last, in $L$, element $e_\ell$ of $E(\mathcal{M})\setminus E_a$ belongs in $E_c$. Note then that all edges of $E_b$ appear in $L$ after $e_1 \in E_a$ and before $e_\ell \in E_c$.

By the definition of fusion follows that $\mathcal{M}/(E_a \cup E_c) = \mathcal{M}_b$. Consider the matroid $\mathcal{M}' = \mathcal{M}/(E_b \setminus e_b)$ and observe that $\mathcal{M}' = S(S(\mathcal{U}_{1,3}, \mathcal{M}_a), \mathcal{M}_c)$. Let $L_b = (e_{p_1}, \dots, e_{p_s})$ be the restriction of $L$ in $E(\mathcal{M}_b)$. As $\mathbf{pw}(\mathcal{M}_b) \ge k$, there is an $h \in \{1, \dots, s-1\}$ such that $\lambda_{\mathcal{M}_b}(F_b) \ge k$, where $F_b = \{e_{p_1}, \dots, e_{p_h}\} \subseteq E_b$. Let $F' = \{e_j \in L \mid e_j \notin E_b \text{ and } j < p_h\}$.

Observe now that $F' \subseteq E_a \cup E_c$ and $\{e_1, \dots, e_{p_h}\} = F_b \cup F'$. Since $E(\mathcal{M}'\setminus e_b) = E_a \cup E_c$, it also holds that $F' \subseteq E(\mathcal{M}'\setminus e_b)$. From Observation 1, $\mathcal{M}'$ can be seen as a parallel connection of two matroids on the element $e_b$. This, together with Fact 2 implies that $\mathcal{M}'/e_b$ is not connected. By Fact 1, it follows that the matroid $\mathcal{M}'\setminus e_b$ is connected.

By the connectivity of $\mathcal{M}'\setminus e_b$ and the fact that $e_1 \in F'$, $e_\ell \notin F'$ we obtain that $\lambda_{\mathcal{M}^\ell e_b}(F') \ge 1$. Observe finally that $\mathcal{M}' \cap \mathcal{M}_b = \{e_b\}$ and $\mathcal{M} = S(\mathcal{M}', \mathcal{M}_b)$. Applying Lemma 2 implies that $\lambda_{\mathcal{M}}(F_b \cup F') \ge k+1$. As $\{e_1, \dots, e_{p_h}\} = F_b \cup F'$, we can choose $q = p_h$. $\square$

## 4. $\mu$-Pathwidth and Linear Width

Let $\mathcal{T}$ be the set of all trees. We define the function $\phi$ that maps trees to graphs such that for every $T \in \mathcal{T}$, $\phi(T)$ is the graph obtained if we identify all the leaves of $T$ to a single vertex (see Figure 1 for an example). We denote the new vertex as the *join-vertex* of $\phi(T)$.

<figure><img src="image_2.png" /><figcaption>Figure 1: An example of the application of the function $\phi$.</figcaption></figure>

Observe that if $G$ is a 2-connected outerplanar graph, then its dual $H$ belongs to the class $\phi(\mathcal{T})$, where its join-vertex corresponds to the outer face of $G$.

Let $G$ be a graph. For any set of edges $F \subseteq E(G)$ we denote by $\partial_G(F)$ the set of vertices of the graph that are incident with an edge in $F$ and also
with an edge in $E(G) \setminus F$. The boundary function $\delta_G(F)$ of the graph $G$ is defined as $\delta_G(F) = |\partial_G(F)|$. We define the linear width of a graph $G$ as the minimum integer $k$ for which there exists a layout $L = (e_1, \dots, e_m)$ of the edge set $E(G)$, such with $\max\{\delta_G(\{e_1, \dots, e_i\}) \mid 1 \le i \le m-1\} \le k$ and we write $\text{lw}(G) \le k$.

Given a graph $G$ and an edge set $F \subseteq E(G)$ as before, we denote by $\sigma_G(F)$ the number of the connected components of $G[F]$. We will need the following well known fact (see, e.g. [16, 15, 6]).

**Fact 3.** Let $G$ be a connected graph and $F \subseteq E(G)$. Then $\lambda_{M(G)}(F) = \delta_G(F) - \sigma_G(F) - \sigma_G(\bar{F}) + 1$.

Using this fact we can prove the following relation between the linear width of a tree $T$ and the $\mu$-pathwidth of $\phi(T)$.

**Lemma 4.** For every tree $T$, it holds that $\mu$-pw($\phi(T)$) $\le$ lw($T$).

**Proof.** Let $F$ be an edge set in $E(T)$, where $F \neq \emptyset$ and $F \neq E(T)$. By the definition of the function $\phi$, the tree $T$ and the graph $H = \phi(T)$ share a common edge set. Note that only inner vertices of $T$ contribute to $\delta_T(F)$ and observe that the corresponding vertices of $H$, with the possible addition of the vertex $v$, into which the leaves of $T$ merged, are the ones that contribute to $\delta_H(F)$; i.e. $\delta_H(F) \le \delta_T(F) + 1$. From Fact 3, we obtain that $\lambda_{M(H)}(F) = \delta_H(F) - \sigma_H(F) - \sigma_H(\bar{F}) + 1 \le \delta_H(F) - 1 \le \delta_T(F)$. It is straightforward now to conclude that given any sequence of $E(T)$ that results to $\text{lw}(T) \le l$, the same sequence results to $\mu$-pw($H) \le l$. $\square$

We recursively define the parameterized family of trees $\mathcal{T}_k$, for any non-negative integer $k$, as follows:

* Let $\mathcal{T}_0$ contain the tree obtained by the 1-subdivision of $K_2$.

* For $k \ge 1$, $\mathcal{T}_k$ contains any tree that can be obtained by the following procedure: Take three (not necessarily distinct) members of $\mathcal{T}_{k-1}$, add a new vertex and connect it with some non-leaf vertex in each of these three trees. As long as a leaf in the resulting graph has a neighbour of degree 3, delete this leaf.

For an example of the above construction, see Figure 2 (only two of the four members of the class $\mathcal{T}_2$ are depicted in Figure 2).

We denote by $\mathcal{L}_k$ the class of graphs with linear-width at most $k$. Linear-width is a parameter defined in [21] and studied in [4, 20]. While it differs
<figure><img src="image_3.png" /><figcaption>Figure 2: The classes $\mathcal{T}_0$, $\mathcal{T}_1$, and part of $\mathcal{T}_2$.</figcaption></figure>

by at most one from the more known parameter of pathwidth, it is more
easy to study in our context because of the strong similarity of its definition
to the one of $\mu$-pathwidth.

The acyclic obstructions for $\mathcal{L}_k$ are determined by the following result
(see Theorem 29 in [20]).

**Proposition 1.** For every non-negative integer $k$, $\text{obs}(\mathcal{L}_k) \cap \mathcal{T} = \mathcal{T}_k$.

**5. Obstructions for $\mu$-Pathwidth**

For each non-negative integer $k$, we define $\mathcal{H}_k = \phi(\mathcal{T}_k)$, i.e. a graph $H$ belongs to the class $\mathcal{H}_k$, iff $H = \phi(T)$ for some $T \in \mathcal{T}_k$ (see Figure 3).

<figure><img src="image_4.png" /><figcaption>Figure 3: The sets $\mathcal{H}_0$, $\mathcal{H}_1$, and part of $\mathcal{H}_2$.</figcaption></figure>

Let now $G_1, G_2, G_3$ be three disjoint 2-connected graphs and $v_i, u_i \in V(G_i)$ a pair of distinct vertices for $i = \{1, 2, 3\}$. We call *u-fusion* of the graphs $G_1, G_2, G_3$ on the given pairs of vertices the graph $G$ constructed as follows:

a) For $i = \{1, 2, 3\}$ if the vertices $v_i, u_i$ are adjacent in $G_i$, then delete the edge $\{v_i, u_i\}$ in $G_i$ (in case $\{v_i, u_i\}$ is a multiple edge, delete only one of its copies).

b) Identify vertices $v_1, v_2, v_3$ to a single vertex $v$, take a new vertex $u$ not in $G_1, G_2$ or $G_3$, and add the edges $\{u_1, u\}, \{u_2, u\}$ and $\{u_3, u\}$.
<figure><img src="image_5.png" /><figcaption>Figure 4: The *u*-fusion operation.</figcaption></figure>

Notice that $G$ is 2-connected by construction. We will call the vertices $v, u$ base vertex and top vertex of the resulting graph respectively and the three edges incident to $u$ bridge edges in $G$.

**Lemma 5.** Let $G$ be a $u$-fusion of three disjoint 2-connected graphs $G_1, G_2$ and $G_3$. Then $\mu$-$pw(G) \ge \min\{\mu$-$pw(G_1), \mu$-$pw(G_2), \mu$-$pw(G_3)\} + 1$.

**Proof.** For $i = 1, 2, 3$ let us denote by $v_i, u_i \in V(G_i)$ the pair of vertices involved in the $u$-fusion of the three graphs. Consider for each graph $G_i$ the graph $G_i^+$ which has the same vertex set as $G_i$ and edge set $E(G_i^+) = E(G_i)$ if $e_i = \{v_i, u_i\} \in E(G_i)$ or else $E(G_i^+) = E(G_i) \cup e_i$. Clearly $\mu$-$pw(G_i^+) \ge \mu$-$pw(G_i)$ for $i = 1, 2, 3$.

Recall that, by its definition, a matroid formed as a fusion of three graphic matroids is itself graphic as the class of graphic matroids is closed under series connection. By construction, the cycle matroid of $G$ is isomorphic to the matroid obtained by the fusion of the cycle matroids of the graphs $G_1^+, G_2^+, G_3^+$ on the elements $e_1, e_2, e_3$. Then, the application of Lemma 3 yields that $\mu$-$pw(G) \ge \min\{\mu$-$pw(G_1), \mu$-$pw(G_2), \mu$-$pw(G_3)\} + 1$. $\square$

We will use Lemma 5 to prove the following lemma:

**Lemma 6.** Let $H$ be a graph in $\mathcal{H}_k$ for some non-negative integer $k$. Then $H$ is an obstruction for $\mu$-pathwidth less or equal to $k$.

**Proof.** Following the standard course for a proof of an obstruction set let us first attend to the value of the $\mu$-pathwidth of a given graph in $\mathcal{H}_k$. Notice that $\mu$-$pw(C_2) = 1$ and that, for any $k \ge 1$, every graph in $\mathcal{H}_k$ is 2-connected, i.e. its cycle matroid is connected. Since every graph in $\mathcal{H}_k$ is a $u$-fusion of three graphs of the class $\mathcal{H}_{k-1}$, by applying inductively Corollary 5 it follows that for any integer $k \ge 0$, all graphs in $\mathcal{H}_k$ have $\mu$-pathwidth at least $k+1$. On the other hand a graph in $\mathcal{H}_k$ has clearly $\mu$-pathwidth at most $k+1$, as otherwise its image in $\mathcal{T}_k$ over $\phi^{-1}$ would have
also linear width more than $k+1$ by Lemma 4. Summarizing, all graphs in $\mathcal{H}_k$ for $k \ge 0$ have $\mu$-pathwidth equal to $k+1$.

Consider now such a graph $H$ in $\mathcal{H}_k$ and also the tree $T = \phi^{-1}(H)$. For an edge $e$ in $E(H) = E(T)$, we examine the graph $H/e$ and the tree $T/e$. Since $T$ belongs in $\mathcal{T}_k$ all leaves have neighbors of degree 2 and therefore $T/e$ is again a tree with the same number of leaves. Moreover, both $T/e$ and the cycle matroid of $H/e$ are connected. It follows that $H/e = \phi(T/e)$ and hence by Lemma 4, $\mu$-pw$(H/e) \le k$, as $T$ is an obstruction for linear width of at most $k$.

Similarly, we examine the graph $H\e$ and the tree $T\e$. Since the cycle matroid $M(H\e)$ is not connected, it does not hold that $H\e = \phi(T\e)$. However, each connected block $M_i$ in $M(H\e)$ is the cycle matroid of $\phi(T_i)$, where $T_i$ is a minor of $T\e$. In any case, again Lemma 4 immediately implies that $\mu$-pw$(H\e) \le k$. $\square$

Conversely, we will prove that if the dual of a biconnected outerplanar graph is an obstruction to $\mu$-pathwidth then it belongs to the family $\mathcal{H}_k$.

**Lemma 7.** Let $H$ be the dual of a biconnected outerplanar graph that is an obstruction for $\mu$-pathwidth at most $k$. Then $H \in \mathcal{H}_k$.

**Proof.** To a contradiction, suppose that $H$ does not belong to the family $\mathcal{H}_k$. Since $H$ is an obstruction for $\mu$-pathwidth at most $k$, surely $\mu$-pw$(H) \ge k+1$ and Lemma 4 implies $\text{lw}(T) \ge k+1$, for the corresponding tree $T = \phi^{-1}(H)$. Thus it contains a minor $T' \subseteq T$ such that $T' \in \mathcal{T}_{k+1}$. Consider now $H' = \phi(T')$ and observe that $H' \subseteq H$; a contradiction since by definition $H' \in \mathcal{H}_{k+1}$. $\square$

For every non-negative integer $k$, we define $\mathcal{H}_k^*$ as the class of all duals of the graphs in $\mathcal{H}_k$ (see Figure 5). The previous two lemmata, along with Lemma 1, imply the main result of our paper.

**Theorem 1.** For every non-negative integer $k$, the set $\mathcal{H}_k^*$ is the obstruction set for the class outerplanar graphs with $\mu$-pathwidth at most $k$.

The theorem reveals a bijection between the acyclic obstructions for linear width and the outerplanar obstructions for $\mu$-pathwidth. This also gives a way to lower bound the size of $\mathcal{P}_k$. Copying the counting made in [19] (see also [20]), it follows that $|\text{obs}(\mathcal{P}_k)| \ge (k!)^2$.

Another consequence of our results is the following.

**Corollary 1.** Let $G$ be a biconnected outerplanar graph and let $T$ be a tree such that $G^* = \phi(T)$. Then $\mu$-pw$(G) = \text{lw}(T)$.
<figure><img src="image_6.png" /><figcaption>Figure 5: The sets $\mathcal{H}_0^*$, $\mathcal{H}_1^*$ and part of $\mathcal{H}_2^*$.</figcaption></figure>

The later implies the existence of a linear time algorithm for the computation of the $\mu$-pathwidth of outerplanar graphs:

**Corollary 2.** *There exists a linear algorithm that, given an outerplanar graph, outputs its $\mu$-pathwidth.*

**Proof.** Let $G$ be an outerplanar graph. Let also $G_1, \dots, G_r$ be its biconnected components and $H_1, \dots, H_r$ their corresponding duals. Let

$$k = \max\{\mathbf{lw}(\phi^{-1}(H_i)) \mid i = 1, \dots, r\}.$$

The linear-width of trees can be computed in linear time, using a straightforward adaptation of the linear algorithm of [18] for computing the path-width of a graph. Therefore, from Corollary 1 and Lemma 1 we have that $\mu$-pw($G$) = $k$. □

[1] Brian Beavers and James Oxley. Constructive characterizations of 3-connected matroids of path width three. *Eur. J. Comb.*, 29(7):1643–1661, 2008.

[2] Thomas H. Brylawski. A combinatorial model for series-parallel networks. *Trans. Amer. Math. Soc.*, 154:1–22, 1971.

[3] 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.

[4] Fedor V. Fomin, Pinar Heggernes, and Rodica Mihai. Mixed search number and linear-width of interval and split graphs. *Networks*, 56(3):207–214, 2010.
[5] J. F. Geelen, A. M. H. Gerards, N. Robertson, and G. P. Whittle. On the excluded minors for the matroids of branch-width *k*. *J. Combin. Theory Ser. B*, 88(2):261–265, 2003.

[6] James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. *J. Combin. Theory Ser. B*, 84(2):270–290, 2002.

[7] Jim Geelen, Bert Gerards, and Geoff Whittle. On Rota's conjecture and excluded minors containing large projective geometries. *J. Combin. Theory Ser. B*, 96(3):405–425, 2006.

[8] Rhiannon Hall, James Oxley, and Charles Semple. The structure of 3-connected matroids of path width three. *European J. Combin.*, 28(3):964–989, 2007.

[9] Rhiannon Hall, James Oxley, Charles Semple, and Geoff Whittle. Fork-decompositions of matroids. *Adv. in Appl. Math.*, 32(3):523–575, 2004.

[10] Illya V. Hicks and Nolan B. McMurray, Jr. The branchwidth of graphs and their cycle matroids. *J. Combin. Theory Ser. B*, 97(5):681–692, 2007.

[11] Petr Hliněný. The Tutte polynomial for matroids of bounded branch-width. *Combin. Probab. Comput.*, 15(3):397–409, 2006.

[12] Jisu Jeong, O joung Kwon, and Sang il Oum. Excluded vertex-minors for graphs of linear rank-width at most *k*. In Natacha Portier and Thomas Wilke, editors, *30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)*, volume 20 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 221–232, Dagstuhl, Germany, 2013. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[13] Navin Kashyap. Matroid pathwidth and code trellis complexity. *SIAM J. Discrete Math.*, 22(1):256–272, 2008.

[14] Daniel Král'. Computing representations of matroids of bounded branch-width. In Wolfgang Thomas and Pascal Weil, editors, *STACS 2007*, volume 4393 of *LNCS*, pages 224–235. Springer Berlin / Heidelberg, 2007.
[15] Frédéric Mazoit and Stéphan Thomassé. Branchwidth of graphic ma-
troids. In *Surveys in combinatorics 2007*, volume 346 of *London Math.
Soc. Lecture Note Ser.*, pages 275–286. Cambridge Univ. Press, Cam-
bridge, 2007.

[16] James G. Oxley. *Matroid theory*. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1992.

[17] T. D. Parsons. Pursuit-evasion in a graph. In *Proceedings Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976, Theory and applications of graphs*, pages 426–441. Lecture Notes in Math., Vol. 642. Springer, Berlin, 1978.

[18] Konstantin Skodinis. Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. *J. Algorithms*, 47(1):40–59, 2003.

[19] Atsushi Takahashi, Shuichi Ueno, and Yoji Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width. *Discrete Mathematics*, 127(1/3):293–304, 1994.

[20] Dimitrios M. Thilikos. Algorithms and obstructions for linear-width and related search parameters. *Discrete Applied Mathematics*, 105:239–271, 2000.

[21] Robin Thomas. Tree-decompositions of graphs. Lecture notes, School of Mathematics. Georgia Institute of Technology, Atlanta, Georgia 30332, USA, 1996.

[22] W. T. Tutte. Connectivity in matroids. *Canad. J. Math.*, 18:1301–1324, 1966.