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

HAL
open science

# Pathlength of outerplanar graphs

Thomas Dissaux, Nicolas Nisse

► To cite this version:

Thomas Dissaux, Nicolas Nisse. Pathlength of outerplanar graphs. Theoretical Computer Science, 2026, 1066, pp.115759. 10.1016/J.TCS.2026.115759. hal-05522106

HAL Id: hal-05522106

https://inria.hal.science/hal-05522106v1

Submitted on 21 Feb 2026

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Pathlength of Outerplanar graphs*

Thomas Dissaux and Nicolas Nisse

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

## Abstract

A *path-decomposition* of a graph $G = (V, E)$ is a sequence of subsets of $V$, called *bags*, that satisfy some connectivity properties. The *length* of a path-decomposition of a graph $G$ is the greatest distance (in $G$) between two vertices that belong to a same bag and the *pathlength*, denoted by $p\ell(G)$, of $G$ is the smallest length of its path-decompositions. This parameter has been studied for its algorithmic applications for several classical metric problems like the minimum eccentricity shortest path problem, the line-distortion problem, etc. However, deciding if the pathlength of a graph $G$ is at most 2 is NP-complete, and the best known approximation algorithm has a ratio 2 (there is no $c$-approximation with $c < \frac{3}{2}$ unless $P = NP$). In this work, we focus on the study of the pathlength of simple sub-classes of planar graphs. We start by designing a linear-time algorithm that computes the pathlength of trees. Then, we show that the pathlength of cycles with $n$ vertices is equal to $\lfloor \frac{n}{2} \rfloor$. Our main result is a (+1)-approximation algorithm for the pathlength of outerplanar graphs. This algorithm is based on a characterization of almost optimal (of length at most $p\ell(G) + 1$) path-decompositions of outerplanar graphs.

**Keywords:** Path-decomposition, outerplanar graph, pathlength.

## 1 Introduction

Path-decompositions of graphs have been extensively studied since their introduction in the Graph Minor theory by Robertson and Seymour, for their various algorithmic applications. A *path-decomposition* of a graph $G = (V, E)$ is a sequence $(X_1, \dots, X_p)$ of subsets (called *bags*) of $V$ such that

1. $\bigcup_{i \le p} X_i = V,$

2. for all edges $\{u, v\} \in E$, there exists $1 \le i \le p$ such that $u, v \in X_i$, and

3. for all $1 \le i \le z \le j \le p$, $X_i \cap X_j \subseteq X_z$.

<footnote>*This work is partially funded by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004). An extended abstract of this work has been presented at LATIN'22 [9]. Corresponding author: nicolas.nisse@inria.fr</footnote>
These constraints imply this fundamental property (widely used in proofs): for all $1 \le i < p$, $S = X_i \cap X_{i+1}$ separates $A = \bigcup_{j \le i} X_j \setminus S$ and $B = \bigcup_{j \ge i} X_j \setminus S$ (i.e., every path between $A$ and $B$ goes through $S$).

The most classical measure of path-decompositions is their *width* corresponding to the maximum size of the bags (minus one). The *pathwidth* of a graph $G$ is the minimum width of its path-decompositions. Typically, the famous theorem of Courcelle implies that numerous NP-hard problems can be solved in polynomial times in graphs of bounded pathwidth [3].

We focus on another measure of path-decomposition which, while less studied, has also numerous algorithmic applications. This measure, the length $\ell(D)$ of a path-decomposition $D$, is the maximum diameter of the bags of $D$, where the diameter $\ell(X)$ of a bag $X$ is the largest distance (in $G$) between two vertices of $X$. The *pathlength* $p\ell(G)$ of a graph $G$, is the minimum length among all its path-decompositions [10]. In particular, this measure captures several metric properties of graphs. For example, the line distortion problem can be approximated (up to a constant factor) when the pathlength is bounded by a constant [11], which has many applications in computer vision [23], computational chemistry and biology [16], in network design and distributed protocol [14], etc. Moreover, since the pathlength is an upper bound on the treelength, the Traveling Salesman Problem admits a FPTAS in bounded pathlength graphs [18], efficient compact routing schemes and sparse additive spanners can be built in the class of graphs with bounded pathlength [17], and computing the *metric dimension* is FPT in the pathlength plus the maximum degree [1], etc.

Unfortunately, deciding if the pathlength of a graph is at most 2 is NP-complete and there does not exist a $c$-approximation for any $c < \frac{3}{2}$ (unless $P = NP$) [13]. On the other hand, there exists a 2-approximation in general graphs [11]. While computing the pathwidth of planar graphs is known to be NP-complete [22], the case of pathlength has not been studied yet. In this paper, we initiate this study by considering outerplanar graphs. Note that the pathwidth of outerplanar graphs is known to be polynomial-time solvable, but the best known algorithm to compute the pathwidth of outerplanar $n$-node graphs has complexity $O(n^{11})$ [4]. Moreover, there exist 2-approximations for this problem, with time complexity $O(n \log(n))$, that deal with the problem by relating the pathwidth of an outerplanar graph with the one of its weak dual [4, 7].

**Our contributions.** In Section 3, we first present a linear-time algorithm that computes the pathlength of trees, and prove that $p\ell(C_n) = \lfloor \frac{n}{2} \rfloor$ for any cycle $C_n$ with $n$ vertices. Section 4 is devoted to our main contribution. We design an algorithm that computes, in time $O(n^3(n + p\ell(G)^2))$, a path-decomposition of length at most $p\ell(G) + 1$ for any outerplanar $n$-node graph $G$. This algorithm is based on a structural characterization of almost optimal (of length at most $p\ell(G) + 1$) path-decompositions of outerplanar graphs.

**Related work.** Path-decompositions are restrictions of the well studied tree-decompositions [5]. The length of a tree-decomposition is the maximum diameter of its bags and the *treelength* of a graph $G$ is the minimum length of its tree-decompositions [2, 6, 10]. Deciding if the treelength of a graph is at most 2 is NP-complete [19]. Some subclasses of planar graphs have also been studied. The treelength of $C_n$ equals $\lfloor \frac{n}{3} \rfloor$ and it follows that the treelength of an outerplanar with largest isometric cycle of length $x$ equals $\lfloor \frac{x}{3} \rfloor$ [10]. Moreover, it was shown that it can be decided in polynomial time whether a series-parallel
graph has treelength at most 2 [8]. However, the case of graphs with treewidth at most 2 is not fully understood.

## 2 Preliminaries

Let $G = (V, E)$ be any graph. When it will not be specified below, $n$ will always be the number $|V|$ of vertices. In what follows, any edge $e = \{x, y\}$ is also considered as the set of two vertices $x$ and $y$. In particular, we say that $X \subseteq V$ contains $e$ if $e \subseteq X$. Given a vertex $v \in V$, let $N(v) = \{u \in V \mid \{v, u\} \in E\}$ be the neighborhood of $v$ and let $N[v] = N(v) \cup \{v\}$ be its closed neighborhood. Given $S \subseteq V$, let $N(S) = \{v \in V \setminus S \mid \exists u \in S, \{u, v\} \in E\}$ and let $G[S] = (S, E \cap (S \times S))$ be the subgraph of $G$ induced by the vertices of $S$. The distance $\text{dist}_G(u, v)$ (or $\text{dist}(u, v)$ if there is no ambiguity) between $u \in V$ and $v \in V$ is the minimum length (number of edges) of a path between $u$ and $v$ in $G$. A subgraph $H$ of $G$ is isometric if $\text{dist}_H(u, v) = \text{dist}_G(u, v)$ for all $u, v \in V(H)$.

A path-decomposition of $G$ is a sequence $D = (X_1, \dots, X_p)$ of subsets of vertices, called bags, such that $\bigcup_{i \le p} X_i = V$, for every $e \in E$, there exists $i \le p$ with $e \subseteq X_i$ and, for every $1 \le i \le j \le q \le p$, $X_i \cap X_q \subseteq X_j$. The length $\ell(D)$ of $D$ is the maximum diameter of one of its bags, i.e., $\ell(D) = \max_{i \le p} \ell(X_i) = \max_{u,v \in X_i} \text{dist}_G(u, v)$. The pathlength $p\ell(G)$ of $G$ is the minimum length of its path-decompositions. A path-decomposition of $G$ of length $p\ell(G)$ is said to be optimal.

Let us say that a path-decomposition is reduced if no bag is contained in another one. It is easy to check that any graph admits an optimal reduced path-decomposition. In what follows, we will use the following result.

**Lemma 1** [10] For every isometric subgraph $H$ of $G$, $p\ell(H) \le p\ell(G)$.

An alternative (equivalent) way to define path-decompositions of a graph $G = (V, E)$ is through orderings of $V$. This representation will be particularly useful in Section 4. Let $\mathcal{O} = (v_1, \dots, v_n)$ be an ordering (i.e., a permutation) of $V$. Let $D(\mathcal{O}) = (X_1, \dots, X_{2n-2})$ be defined as follows. Let $X_1 = \{v_1\}$ and, for every $2 \le i < n$, let $X_{2i-2} = X_{2i-3} \cup \{v_i\}$, let $S_i \subseteq X_{2i-2}$ be the set of vertices $x \in X_{2i-2}$ such that $N[x] \subseteq \bigcup_{j \le 2i-2} X_j$ (i.e., all vertices of $X_{2i-2}$ whose all neighbors belong to a bag $X_j$ for some $j \le 2i-2$) and let $X_{2i-1} = X_{2i-2} \setminus S_i$. In particular, note that $S_i \subseteq N[v_i]$ and may be empty. Finally, let $X_{2n-2} = X_{2n-3} \cup \{v_n\}$. The following observation is straightforward.

**Observation 1** Let $\mathcal{O}$ be any ordering of the vertex-set $V$ of a graph $G = (V, E)$. Then, $D(\mathcal{O})$ is a (not reduced) path-decomposition of $G$.

Given an ordering $\mathcal{O} = (v_1, \dots, v_n)$ and $1 \le i \le j \le n$, let $\mathcal{O}[v_i, v_j] = (v_i, \dots, v_j)$.

Given two sequences $D = (X_1, \dots, X_p)$ and $D'$ of subsets of $V$ and $S \subseteq V$, let $D \cup S = (X_1 \cup S, \dots, X_p \cup S)$ (If $S = \{v\}$, we write $D \cup v$ instead of $D \cup \{v\}$). Let $D \cap S$ and $D \setminus S$ be defined in a similar way (in these cases, the empty bags that may be created are removed). Finally, let $D \odot D'$ be the sequence obtained by the concatenation of $D$ and $D'$. The following observation is straightforward (and well known).

**Observation 2** Let $D$ be a path-decomposition of $G = (V, E)$ and $S \subseteq V$.
1. Then, $D' = D \cap S$ (resp., $D' = D \setminus S$) is a path-decomposition of $G[V \cap S]$ (resp., of $G \setminus S$). Moreover, if $G[V \cap S]$ (resp., $G \setminus S$) is an isometric subgraph of $G$, then $\ell(D') \le \ell(D)$.

2. Let $D'$ be a path-decomposition of $G[V \setminus S]$. Then, $D' \cup S$ is a path-decomposition of $G$.

3. Let $V = A \cup B$ with $A \cap B = S$ and $S$ separating $A \setminus S$ and $B \setminus S$ (there does not exist any edge $\{u, v\} \in E$ with $u \in A \setminus S$ and $v \in B \setminus S$), let $D_1$ be a path-decomposition of $G[A]$ with last bag containing $S$, and let $D_2$ be a path-decomposition of $G[B]$ with the first bag containing $S$. Then, $D_1 \odot D_2$ is a path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\}$.

# 3 Pathlength of trees and cycles

We first begin by the trees, the "simplest" sub-class of planar graphs. Note that, intuitively, the algorithm presented in Section 4, that computes the pathlength of outerplanar graphs follows similar ideas as the one we present for trees.

Let $k \in \mathbb{N}$ and let $S_k$ be the tree obtained from a star with three leaves by subdividing each edge $k$ times, i.e., by replacing each edge by a path with $k+1$ edges.

**Lemma 2** [10] For any $k \in \mathbb{N}$, $\mathbf{p}\ell(S_k) = k + 1$.

Note that, $\mathbf{p}\ell(S_k) = \frac{|V(S_k)|-1}{3}$. This is in contrast to the width counterpart where the pathwidth of any $n$-node tree is at most $O(\log n)$.

**Theorem 1** The pathlength of any tree and an optimal path-decomposition can be computed in linear time.

**Proof.** Let $T$ be any tree. If $T$ is a path, the result is obvious (the pathlength equals one), so we may assume that $T$ has at least three leaves.

Let $P_0$ be a longest path in $T$ and let $x$ and $y$ be its endpoints (that are leaves). Let $z$ be any leaf of $T$ maximizing its distance to $P_0$ (i.e., for any leaf $f$ of $T$, $\text{dist}(f, P_0) = \min_{v \in V(P_0)} \text{dist}(f, v) \le \text{dist}(z, P_0)$). Let $v^*$ be the projection of $z$ on $P_0$, i.e., $v^*$ is the vertex of $P_0$ minimizing its distance to $z$. Note that $\text{dist}(v^*, z) \le \min\{\text{dist}(v^*, x), \text{dist}(v^*, y)\}$ (since otherwise, $P_0$ would not be a longest path). Let $T'$ be the inclusion-minimal subtree of $T$ containing $x$, $y$ and $z$. Note that $T'$ contains $S_k$ as isometric subgraph for $k = \text{dist}(v^*, z) - 1$, and so, $S_k$ is an isometric subgraph of $T$. Then, by Lemmas 1 and 2, $\mathbf{p}\ell(T) \ge \mathbf{p}\ell(S_k) = k + 1$.

We now show that $\mathbf{p}\ell(T) = k + 1$ by building a path-decomposition $D$ of $T$ with length $k+1$. Let $P_0 = (x = v_0, v_1, \dots, v_t = y)$. Let us describe an iterative algorithm that builds $D$. Let us start with $D$ containing only the bag $\{v_0, v_1\}$.

For $i$ going from 1 to $t-1$, let us do the following. Let $T^i$ be the connected component of $T \setminus E(P_0)$ (that is, removing the edges of $P_0$ but keeping its vertices) that contains $v_i$. Let $F^i$ be the sequence of leaves of $T^i$ except $v_i$ (if $v_i$ is a leaf of $T^i$) ordered by following any DFS of $T^i$ starting from $v_i$. Note that, by definition of $z$, for every $f \in F^i$, $\text{dist}(f, v_i) \le k+1$ (let us denote this Property by (**))). Let $Q = (Q_1, \dots, Q_{|F^i|})$ be the
<figure><img src="image_3.png" /><figcaption>Figure 1: Example of a tree $T$ (with $\mathbf{p}\ell(T) = 2$) and a possible optimal path-decomposition $(\{ab\}, \{bc\}, X, Y, \{cd\}, \{de\}, Z, W, \{ef\}, \{fg\})$ obtained from Theorem 1.</figcaption></figure>

sequence of the paths from $v_i$ to $f$, for every $f \in F^i$, where the ordering of the paths follows the ordering of the leaves in $F^i$. For $q$ going from 1 to $|F^i|$, add $V(Q_q)$ as the next bag of $D$, and then, add the bag $\{v_i, v_{i+1}\}$ to $D$. An example of such a decomposition is given in Figure 1.

Let $D = (X_1, \dots, X_h)$ be the outcome of the above algorithm. First, by Property (\*\*), for every $1 \le i \le h$, $\ell(X_i) = \max_{u,v \in X_i} \mathrm{dist}_G(u, v) \le k+1$. Hence, it remains to prove that $D$ is a path-decomposition of $T$. By construction, it is clear that every vertex and every edge of $T$ belong to at least one bag of $D$. Moreover, for every $1 \le j \le t$, again by construction, if $v_j \in X_a \cap X_b$, then $v_j \in X_c$ for every $a \le c \le b$. Finally, let $v \in V(T) \setminus V(P_0)$, let $1 \le i < t$ such that $v \in V(T^i)$ and assume that $v$ belongs to $X_a \cap X_b$ for $1 \le a < b \le h$. By construction, there are two leaves $f_a$ and $f_b$ of $T^i \setminus \{v_i\}$ such that $v$ belongs to $P_a$ and $P_b$, the path between $v_i$ and $f_a$ and the path between $v_i$ and $f_b$ respectively, and with $X_a = V(P_a)$ and $X_b = V(P_b)$. Moreover, $f_a < f_b$ in the ordering of $F^i$. Now, for every $a \le c \le b$, the bag $X_c$ corresponds to the path $P_c$ between $v_i$ and a leaf $f_c$ of $T^i \setminus \{v_i\}$ such that $f_a \le f_c \le f_b$ in the ordering of $F^i$. By definition of the DFS of $T^i$ from $v_i$, the path $P_c$ must also contain $v$ and so $v \in X_c = V(P_c)$. Hence, $D$ is a path-decomposition of $T$ with length at most $k+1$.

The fact that the above algorithm can be done in linear time comes from the fact that $P_0$ can be computed in linear time (the diameter of a tree can be computed using 2 BFSs) and then, performing one DFS from $v_i$ for each $T^i$ suffices to compute the order of $Q$ for each $T^i$.

**Remark.** The above proof actually shows that, in any tree $T$, $\mathbf{p}\ell(T)$ equals its minimum eccentricity shortest-path. Note that it was already known that the minimum eccentricity shortest-path of trees can be computed in linear time [12].

We will focus now on cycles.

**Theorem 2** Let $C_n$ be a cycle of length $n$. We have that $\mathbf{p}\ell(C_n) = \lfloor \frac{n}{2} \rfloor$.

**Proof.** First, the path-decomposition consisting of a unique bag $V(C_n)$ has length $\lfloor \frac{n}{2} \rfloor$, so, $\mathbf{p}\ell(C_n) \le \lfloor \frac{n}{2} \rfloor$. Let us show that it is an optimal path-decomposition.

For purpose of contradiction, let us suppose that $C_n$ admits a reduced path-decomposition $D = (X_1, \dots, X_p)$ of length $k < \lfloor \frac{n}{2} \rfloor$. First, let us show that we may assume that $X_1$ induces a connected subgraph (more precisely, a sub-path). Let us assume that it is not the case. Since $D$ is reduced, there is a vertex in $X_1$ that is not in every $X_i$ for $2 \le i \le p$. Let $v$ be such a vertex. Since $v$ is only in $X_1$, the two neighbors of $v$ also belong to $X_1$. Let
A be the connected component of $G[X_1]$ containing $v$. Note that $A$ is a path, otherwise $V(A) = V(C_n)$ contradicting that $k < \lfloor \frac{n}{2} \rfloor$. Let $x$ and $y$ be the two endpoints of $A$ and let $A' = A \setminus \{x, y\}$. Then, $D' = (A, X_1 \setminus A', X_2 \setminus A', \dots, X_p \setminus A')$ is a path-decomposition of length at most $k$ and whose first bag induces a path. Up to removing the redundant bags (note that $A$ is not contained in any other bag), we may assume that $D'$ is reduced.

Hence, let $D = (X_1, \dots, X_p)$ be a reduced path-decomposition of length $k < \lfloor \frac{n}{2} \rfloor$ such that $X_1$ induces a path. We moreover assume that, among such decompositions, $D$ maximizes $|X_1|$. We next show that $|X_1| = k+1$. Let $x$ and $y$ be the two ends of the path induced by $X_1$. Note that $|X_1| - 1 = \text{dist}(x, y) \le k$. For purpose of contradiction, let us assume that $\text{dist}(x, y) < k$. Let $x'$ and $y'$ be respectively the neighbors of $x$ and $y$ not in $X_1$. Let $X_j$ and $X_{j'}$ be the first bags (closest to $X_1$) that contain $y'$ and $x'$ respectively. Note that $y \in X_i$ for any $1 \le i \le j$ (resp. $x \in X_{i'}$ for any $1 \le i' \le j'$), otherwise there would be no bag containing the edge $\{y, y'\}$ (resp. the edge $\{x, x'\}$). W.l.o.g., let suppose that $j \le j'$. Therefore, $X_j$ contains $x, y$ and $y'$. Note that $\text{dist}(x, y') = \text{dist}(x, y) + 1 \le k$. Then, $D' = (X_1 \cup \{y'\}, \dots, X_{j-1} \cup \{y'\}, X_j, \dots, X_p)$ is a path-decomposition whose first bag induces a path of length $|X_1|$. We show that $D'$ has length at most $k$ which will contradict the maximality of $|X_1|$ in $D$.

For purpose of contradiction, let us assume that $D'$ has length strictly larger than $k$. Therefore, there exists $1 < h < j$ and $w \in X_h$ such that $\text{dist}(w, y') > k$. Since $y \in X_h$, then $\text{dist}(w, y) \le k$. Note also that $\text{dist}(w, y') \le \text{dist}(w, y) + 1 \le k + 1$ and so $\text{dist}(w, y') = k + 1$. Since $\text{dist}(w, y) \ge \text{dist}(w, y') - 1 = k$, then $w$ is the unique vertex at distance $k$ from $y$ and at distance at least $k+1$ from $y'$. Let $w'$ be the neighbor of $w$ such that $\text{dist}(w', y) = k + 1$. Note that $w'$ cannot be in a bag containing $y$ since they are at distance $k+1$. Therefore, it is not in $X_i$ for $1 \le i \le j$ (since these bags contain $y$). Note that $w'$ and $w$ have to be in some common bag of $D$ (since they are adjacent). Therefore, there is a bag $X_l$ with $j < l \le p$ that contains $w$ and $w'$. Since $w \in X_h \cap X_l$, then $w \in X_j$ which contradicts the fact that $D$ has length at most $k$ (since $\text{dist}(w, y') > k$). Therefore, $D'$ is a path-decomposition of length $k$.

Hence, let $D = (X_1, \dots, X_p)$ be a reduced path-decomposition of length $k < \lfloor \frac{n}{2} \rfloor$ such that $X_1$ induces a path of length exactly $k$. Let $x'$ and $y'$ be the neighbors of $x$ and $y$ not in $X_1$. Let $X_j$ and $X_{j'}$ be the first bags (closest to $X_1$) that contain $y'$ and $x'$ respectively. Note that $y \in X_i$ for any $1 \le i \le j$ (resp. $x \in X_{i'}$ for any $1 \le i' \le j'$). W.l.o.g., let suppose that $j \le j'$. Therefore, $X_j$ contains $x, y$ and $y'$, a contradiction since $x$ and $y'$ are at distance $k+1$ because $k < \lfloor \frac{n}{2} \rfloor$. ■

# 4 Outerplanar graphs

This section is devoted to our main result: a polynomial-time algorithm for computing a path-decomposition of any simple (without parallel edges nor loops) outerplanar graph $G$, with length at most $p\ell(G) + 1$.

A graph $G = (V, E)$ is *outerplanar* if it can be embedded in the plane without crossing edges and such that all vertices lie on the outer face (the unbounded face). An edge of an outerplanar graph is called an *internal edge* if it does not lie on the outer face. Note that, since we only consider simple graphs, the fact that an edge is internal or not does not depend on the outerplanar embedding. Indeed, let $e = \{x, y\}$ be an internal edge in
some outerplanar embedding of $G$. Let $P_{xy}$ and $P'_{xy}$ be the two paths on the outer face between $x$ and $y$. Because $G$ is simple and $e$ is internal, there exist a vertex $u$ of $P_{xy}$ and a vertex $v$ of $P'_{xy}$ both distinct from $x$ and $y$. Consider a planar embedding of $G$ such that $e$ lies on the outer face. By Jordan's theorem [21] and since $e$ is on the outer face, either $v$ is "inside" the cycle $P_{xy} \cup e$, or $u$ is "inside" the cycle $P'_{xy} \cup e$. In both cases, the embedding is not an outerplanar embedding of $G$. Hence, $e$ must be an internal edge in any outerplanar embedding of $G$.

Let $E_{int} \subseteq E$ be the set of internal edges and $E_{out} = E \setminus E_{int}$ be the set of outer edges. Note that any internal edge $e \in E_{int}$ of an outerplanar graph $G = (V, E)$ is a separator (i.e., $G \setminus V(e)$ has several connected components).

**Path-decomposition with fixed first and last elements.** Let $G = (V, E)$ be a connected graph and let $v \in V$ (resp., $e \in E$). A path-decomposition $D = (X_1, \cdots, X_p)$ of $G$ starts from $v$ (resp., from $e$) if $v \in X_1$ (resp., if $e \subseteq X_1$). Similarly, $D$ finishes with $v$ (resp., with $e$) if $v \in X_p$ (resp., if $e \subseteq X_p$). Let $x, y \in V \cup E$, a path-decomposition of $G$ starting from $x$ and finishing with $y$ is called a **$\{x, y\}$-path-decomposition**. Let $\mathfrak{p}\ell(G, x, y)$ be the minimum length among all $\{x, y\}$-path-decompositions of $G$. An $\{x, y\}$-path-decomposition is an **optimal $\{x, y\}$-path-decomposition** if its length is $\mathfrak{p}\ell(G, x, y)$. Clearly, any $\{x, y\}$-path-decomposition $(X_1, \cdots, X_p)$ corresponds to an $\{y, x\}$-path-decomposition $(X_p, \cdots, X_1)$ with the same length, and so:

**Observation 3** For any connected graph $G = (V, E)$ and $x, y \in E \cup V$, $\mathfrak{p}\ell(G, x, y) = \mathfrak{p}\ell(G, y, x)$.

The following observation directly holds by definition and because there always exists a reduced optimal path-decomposition (note that, for any reduced path-decomposition $D$ of a connected graph, there exist $x, y \in E$ such that $D$ starts from $x$ and finishes with $y$).

**Observation 4** For any connected graph $G = (V, E)$, $\mathfrak{p}\ell(G) = \min_{x,y \in E} \mathfrak{p}\ell(G, x, y)$.

For our purpose, we need to refine the above observation as follows.

**Lemma 3** For any connected graph $G = (V, E)$, $\mathfrak{p}\ell(G) = \min_{x,y \in E_{out}} \mathfrak{p}\ell(G, x, y)$.

**Proof.** Let $x, y \in E$ such that $\mathfrak{p}\ell(G) = \mathfrak{p}\ell(G, x, y)$ and such that the "distance" between $x$ and $y$ is maximized (where the distance must be understood here as the number of internal faces that must be crossed to go from $x$ to $y$). Let $D = (X_1, \cdots, X_p)$ be an optimal $\{x, y\}$-path-decomposition of $G$ (so $D$ is an optimal path-decomposition of $G$).

For purpose of contradiction, let us assume that $x \in E_{int}$. Let $C$ be a connected component of $G \setminus x$ that does not contain (nor intersect) $y$. Let $D' = D \cap (C \cup x)$ (note that $\ell(D') \le \ell(D)$ by Observation 2 and because $G \cap (C \cup x)$ is an isometric subgraph of $G$) and $D_2 = D \setminus C$ (note that $\ell(D_2) \le \ell(D)$ by Observation 2 and because $G \setminus C$ is an isometric subgraph of $G$). Let $D''$ be the reduced path-decomposition of $G[C \cup x]$ obtained from $D'$ (i.e., by removing the bags that are contained in others). Since $D''$ is reduced, the last bag of $D''$ must contain an edge $x' \ne x$ of $G[C \cup x]$. Finally, let $D_1$ be the path-decomposition of $G[C \cup x]$ obtained from $D''$ by reversing the order of the bags. Then, $D_1 \odot D_2$ is a $\{x', y\}$-path-decomposition of $G$ of length at most $\mathfrak{p}\ell(G)$ (by
Observation 2 and since $D_1$ and $D_2$ contain $x$ respectively in its last bag and in its first bag), contradicting the maximality of the distance between $x$ and $y$.

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

By Lemma 3, the computation of $\mathbf{p}\ell(G)$ can be restricted to the $O(n^2)$ computations of $\mathbf{p}\ell(G, x, y)$ for all fixed $x, y \in E_{\text{out}}$ (since $G$ is planar, $|E| = O(n)$). Actually, for purpose of induction, we will more generally compute $\mathbf{p}\ell(G, x, y)$ for every fixed $x, y \in E_{\text{out}} \cup V$. Most of what follows is devoted to this task.

**Outline of Section 4.** Therefore, in Sections 4.1 to 4.2, $x, y \in V \cup E_{\text{out}}$ will be fixed. Section 4.1 is devoted to the “easy” cases. Depending on $x$ and $y$, it will sometimes be possible to reduce the problem to smaller instances (and then proceed by induction) and, in other cases (roughly when $x = y$ and $G \setminus x$ is connected), we present a greedy algorithm that computes an optimal $\{x, y\}$-path-decomposition of $G$. Section 4.2 is devoted to the remaining case: roughly, when $x$ and $y$ are distinct, not included in each-other, do not separate $G$ and belong to a same internal (bounded) face of $G$. In this latter case, we show that we can restrict our attention to particular $\{x, y\}$-path-decompositions of $G$ and that such an optimal decomposition can be computed in polynomial time by dynamic programming. Finally, Section 4.3 formally states our main result and describes our main algorithm that uses the results of Sections 4.1 to 4.2 to compute a path-decomposition of a connected outerplanar graph with length at most $\mathbf{p}\ell(G) + 1$.

## 4.1 Cases (depending on $x$ and $y$) when recursion or greedy algorithm are possible

Let $G = (V, E)$ be a connected simple outerplanar graph and let $x, y \in E_{\text{out}} \cup V$. In what follows, recall that an edge is seen as a set of two vertices. In this section, we first show that if $G \setminus x$ is not connected (Section 4.1.1) or if $x$ and $y$ are “separated” (see formal definition in Section 4.1.2), the problem of computing an optimal $\{x, y\}$-path-decomposition of $G$ can be reduced to similar problems in smaller instances. Then, in subsection 4.1.3, roughly, we show that, if none of the previous two properties is met and either $x = y$ or $x \in y$ or $y \in x$, then an optimal $\{x, y\}$-path-decomposition of $G$ can be computed in linear time by a greedy algorithm.

### 4.1.1 Case when $G \setminus x$ is not connected

Let us first assume that $G \setminus x$ is not connected. We have divided this case in several lemmas that look very similar (proofs seem redundant). We have not been able to factorize them while keeping a reasonable readability of this part. In particular, we hope that the division in different lemmas will be helpful to convince that all cases are actually considered.

**Lemma 4** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x = y \in E_{\text{out}} \cup V$ such that $G \setminus x$ is not connected.

Let $C$ be any connected component of $G \setminus x$, let $D_1$ be an optimal $\{x, x\}$-path-decomposition of $G[C \cup x]$ and let $D_2$ be an optimal $\{x, x\}$-path-decomposition of $G \setminus C$. Then, $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.
**Proof.** Let $D$ be an optimal $\{x, x\}$-path-decomposition of $G$. Then, since $C \cup \{x\}$ and $G \setminus C$ are isometric subgraphs of $G$ and by Observation 2, $D \cap (C \cup \{x\})$ is a $\{x, x\}$-path-decomposition of $G[C \cup x]$ of length at most $\ell(D)$ and $D \setminus C$ is a $\{x, x\}$-path-decomposition of $G \setminus C$ of length at most $\ell(D)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

Therefore, in the remaining part of this subsection (i.e., the case where $G \setminus x$ is not connected), we may moreover assume that $x \neq y$.

In the next four lemmas, we consider the cases when $x = \{u, v\} \in E_{out}$, $G \setminus x$ is not connected and $x \neq y$ ($y \in V \cup E_{out}$). Note that, because $x = \{u, v\}$ is not an internal edge, the fact that $G \setminus x$ is not connected implies that one (or both) vertex of $\{u, v\}$ is a cut-vertex.

Precisely, w.l.o.g., we assume that $G \setminus u$ is not connected, and: in Lemmas 5 and 6, we assume that $x \cap y = \{u\}$, and in Lemmas 7 and 8, we consider the cases when $u \notin x \cap y$.

**Lemma 5** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x = \{u, v\} \in E_{out}$, $y \in V \cup E_{out}$ and $x \neq y$, such that $G \setminus u$ is not connected and $\{u\} = x \cap y$. Let $C$ be the connected component of $G \setminus u$ that contains $v$ and assume that $y$ does not intersect $C$.

Let $D_1$ be an optimal $\{x, u\}$-path-decomposition of $G[C \cup x]$ and $D_2$ be an optimal $\{u, y\}$-path-decomposition of $G \setminus C$, then $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D$ be an optimal $\{x, y\}$-path-decomposition of $G$ (note that $u$ belongs to all bags of $D$). By first item of Observation 2 and because $C \cup x$ and $G \setminus C$ are isometric subgraphs of $G$, $D_1 = D \cap (C \cup x)$ is a $\{x, u\}$-path-decomposition of $G[C \cup x]$ of length at most $\mathbf{p}\ell(G, x, y)$ and $D_2 = D \setminus C$ is a $\{u, y\}$-path-decomposition of $G \setminus C$ of length at most $\mathbf{p}\ell(G, x, y)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

**Lemma 6** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x = \{u, v\} \in E_{out}$, $y \in V \cup E_{out}$ and $x \neq y$, such that $G \setminus u$ is not connected and $\{u\} = x \cap y$. Assume that $y$ intersects the connected component $C'$ of $G \setminus u$ that contains $v$ and let $C$ be any connected component of $G \setminus u$ that does not contain $v$.

Let $D_1$ be an optimal $\{x, x\}$-path-decomposition of $G[C \cup x]$ and $D_2$ be an optimal $\{x, y\}$-path-decomposition of $G \setminus C$, then $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D$ be an optimal $\{x, y\}$-path-decomposition of $G$ (note that $u$ belongs to all bags of $D$). By Observation 2 and because $C \cup u$ and $G \setminus C$ are isometric subgraphs of $G$, $D_1 = (D \cap (C \cup u)) \cup v$ is a $\{x, x\}$-path-decomposition of $G[C \cup x]$ of length at most $\mathbf{p}\ell(G, x, y)$ (adding $v$ does not increase the length since all bags of $D$ contain a vertex of
$C'$, i.e., a vertex between $v$ and $y \cap C'$) and $D_2 = D \setminus C$ is an $\{x, y\}$-path-decomposition of $G \setminus C$ of length at most $\mathbf{p}\ell(G, x, y)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

**Lemma 7** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x = \{u, v\} \in E_{\text{out}}, y \in V \cup E_{\text{out}}$ and $x \ne y$, such that $G \setminus u$ is not connected and $u \notin x \cap y$. Let $C$ be the component of $G \setminus u$ that contains $v$ and assume that $C$ does not intersect $y$.

Let $D_1$ be an optimal $\{x, u\}$-path-decomposition of $G[C \cup x]$ and $D_2$ be an optimal $\{u, y\}$-path-decomposition of $G \setminus C$, then $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D$ be an optimal $\{x, y\}$-path-decomposition of $G$. Then, by Observation 2 and because $C \cup u$ and $G \setminus C$ are isometric subgraphs of $G$, $D_1 = (D \cap (C \cup u)) \cup u$ is a $\{x, u\}$-path-decomposition of $G[C \cup x]$ of length at most $\mathbf{p}\ell(G, x, y)$ (this holds since every bag of $D$ contains $u$ or a vertex of the component of $G \setminus u$ that contains $y$) and $D_2 = D \setminus C$ is a $\{u, y\}$-path-decomposition of $G \setminus C$ of length at most $\mathbf{p}\ell(G, x, y)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

**Lemma 8** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x = \{u, v\} \in E_{\text{out}}, y \in V \cup E_{\text{out}}$ and $x \ne y$, such that $G \setminus u$ is not connected and $u \notin x \cap y$. Assume that $y$ is contained in the component $C'$ of $G \setminus u$ that contains $v$. Let $C$ be any connected component of $G \setminus u$ that does not contain $y$.

Let $D_1$ be an optimal $\{x, u\}$-path-decomposition of $G[C \cup x]$ and $D_2$ be an optimal $\{x, y\}$-path-decomposition of $G \setminus C$, then $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D$ be an optimal $\{x, y\}$-path-decomposition of $G$. Then, by Observation 2 and because $C \cup u$ and $G \setminus C$ are isometric subgraphs of $G$, $D_1 = (D \cap (C \cup u)) \cup x$ is a $\{x, u\}$-path-decomposition of $G[C \cup x]$ of length at most $\mathbf{p}\ell(G, x, y)$ (this holds since every bag of $D$ contains a vertex of $C'$ between $v$ and $y \cap C'$ and a vertex of $C'$ between $u$ and $y \cap C'$) and $D_2 = D \setminus C$ is an $\{x, y\}$-path-decomposition of $G \setminus C$ of length at most $\mathbf{p}\ell(G, x, y)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

The case when $x \in V$, $y \in E_{\text{out}}$ and $x \in y$ can be dealt similarly by reversing the path-decomposition (Observation 3).

It only remains the case when $x, y \in V$, $x \ne y$ and $G \setminus x$ is not connected.

**Lemma 9** Let $G = (V, E)$ be a simple connected outerplanar graph and let $x, y \in V$ such that $G \setminus x$ is not connected and $y \ne x$. Let $C$ be any connected component of $G \setminus x$ that does not contain $y$.
Let $D_1$ be an optimal $\{x, y\}$-path-decomposition of $G[C \cup x]$ and $D_2$ be an optimal $\{x, y\}$-path-decomposition of $G\setminus C$, then $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D$ be an optimal $\{x, y\}$-path-decomposition of $G$. Then, by Observation 2 and because $C \cup x$ and $G \setminus C$ are isometric subgraphs of $G$, $D_1 = D \cap (C \cup x) \cup x$ is a $\{x, x\}$-path-decomposition of $G[C \cup x]$ of length at most $\mathbf{p}\ell(G, x, y)$ (this holds since every bag of $D$ contains $x$ or a vertex in $V \setminus C$ since $y$ is in the last bag) and $D_2 = D \setminus C$ is an $\{x, y\}$-path-decomposition of $G \setminus C$ of length at most $\mathbf{p}\ell(G, x, y)$.

By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then clearly, $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$. ■

From now on, we may assume that $G \setminus x$ is connected. For the same reasons and by Observation 3 (and the sentence preceding Observation 3), we may also assume that, $G \setminus y$ is connected.

### 4.1.2 Case when $x$ and $y$ are “separated”

Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{out} \cup V$. In this section, we always assume that $G \setminus x$ and $G \setminus y$ are connected. We say that $x$ and $y$ are separated in $G$ if there exists $z \in V \cup E$ such that $x' = x \setminus z \ne \emptyset$, $y' = y \setminus z \ne \emptyset$ and all paths from $x'$ to $y'$ intersect $z$. Note that this requires that $x \ne y$ and neither $x \in y$ nor $y \in x$, but $x$ and $y$ may intersect (in which case, $z$ is or contains $x \cap y$). Note also that, if $z \in E$ and is inclusion-minimal for the property of separating $x$ and $y$ (i.e., no end of $z$ separates $x$ and $y$), then $z \in E_{int}$.

**Lemma 10** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{out} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, and such that $x$ and $y$ are separated by $z \in V \cup E_{int}$.

Let $C^x$ be the connected component of $G \setminus z$ containing (or intersecting) $x$ and let $C^y = V \setminus C^x$.

Let $D_1$ be an optimal $\{x, z\}$-path-decomposition of $G[C^x \cup z]$ and $D_2$ be an optimal $\{z, y\}$-path-decomposition of $G[C^y]$. Then, $D_1 \odot D_2$ is an optimal $\{x, y\}$-path-decomposition of $G$.

**Proof.** Let $D = (X_1, \dots, X_p)$ be an optimal $\{x, y\}$-path-decomposition of $G$. Let $1 \le i \le p$ be the smallest integer such that $z \in X_i$ (resp., such that $z \subseteq X_i$ if $z$ is an edge) and let $i \le j \le p$ be the largest integer such that $z \in X_j$ (resp., such that $z \supseteq X_j$ if $z$ is an edge). Then, let $D_1 = (X_1 \cap (C^x \cup z), \dots, X_j \cap (C^x \cup z), (X_{j+1} \cap (C^x \cup z)) \cup z, \dots, (X_p \cap (C^x \cup z)) \cup z)$. Clearly, $D_1$ is a $\{x, z\}$-path-decomposition of $G[C^x \cup z]$. Moreover, because $y \in X_p$, then all bags $X_q$ (for $j < q \le p$) must contain some vertex in the connected component of $G \setminus z$ containing $y$. Therefore, since $C^x \cup z$ is an isometric subgraph of $G$ and by Observation 2, $\ell(D_1) \le \ell(D)$. Similarly, let $D_2 = ((X_1 \setminus C^x) \cup z, \dots, (X_{i-1} \setminus C^x) \cup z, X_i \setminus C^x, \dots, X_p \setminus C^x)$. Then, $D_2$ is a $\{z, y\}$-path-decomposition of $G \setminus C^x$. Moreover, because $x \in X_1$, then all bags $X_q$ (for $1 \le q < i$) must contain some vertex in $C^x$. Therefore, since $C^y$ is an isometric subgraph of $G$ and by Observation 2, $\ell(D_2) \le \ell(D)$.
By the last statement of Observation 2, if $D_1$ and $D_2$ are defined as in the statement of the lemma, then clearly, $D_1 \odot D_2$ is an $\{x, y\}$-path-decomposition of $G$ of length at most $\max\{\ell(D_1), \ell(D_2)\} \le \ell(D) = \mathbf{p}\ell(G, x, y)$.

### 4.1.3 Case when $x = y$ or $x \in y$ or $y \in x$: Greedy algorithm

In this section, we show that an optimal $\{x, y\}$-path-decomposition can be computed in linear time when $x = y$ or $x \in y$ or $y \in x$. For this purpose, we design the algorithm **Greedy** to build a particular $\{x, x\}$-path-decomposition (called a decomposition based on $x$) when $x \in E_{out} \cup V$ and does not contain a cut-vertex. First, let us note that:

**Observation 5** Let $G$ be a $n$-node connected simple outerplanar graph and $x \in E_{out} \cup V$. Then, $\mathbf{p}\ell(G, x, x) = 1$ if and only if $G$ is an interval graph and $x$ belongs to every maximal clique.

*Proof of Observation.* It is easy to check that, for every graph $H$, $\mathbf{p}\ell(H) = 1$ if and only if $H$ is an interval graph. Since $\mathbf{p}\ell(G) \le \mathbf{p}\ell(G, x, x)$, then $G$ must be an interval graph. Since $x$ belongs to all bags of any $\{x, x\}$-path-decomposition, the result follows. ◇

**Greedy algorithm.** Let $G = (V, E)$ be a $n$-node connected simple outerplanar graph and $x \in E_{out} \cup V$ (such that no vertex of $x$ is a cut-vertex). First, the algorithm checks whether $\mathbf{p}\ell(G, x, x) = 1$ which can be done easily by Observation 5. If $\mathbf{p}\ell(G, x, x) = 1$, **Greedy**($G$) returns the path-decomposition that consists of the sequence of the maximal cliques in any order. If $\mathbf{p}\ell(G, x, x) > 1$, let $G$ be embedded in the plane using any outerplanar embedding of $G$ (such an embedding can be computed in linear time [20]). Let $\mathcal{O} = (v_1, \dots, v_n)$ be the ordering of $V$ where a vertex appears when it is met for the first time by following clockwise the outer-face of the embedding, starting and finishing in $x$ (that is, either $x = \{v_1, v_n\} \in E_{out}$ or $x = v_1 \in V$). Note that the fact that $x$ contains no cut-vertex ensures that, if $x = \{a, b\} \in E_{out}$, then following the outer-face starting from $a$ necessarily ends in $b$, i.e. $x = \{v_1, v_n\}$. An example is presented in Figure 2. Then, let $D(\mathcal{O}) = (X'_1, \dots, X'_q)$ be the path-decomposition obtained from $\mathcal{O}$ as defined in Section 2 (see Observation 1). The algorithm **Greedy**($G$) returns the path-decomposition $(X'_1 \cup x, \dots, X'_q \cup x)$. Note that this path-decomposition depends on the chosen planar embedding.

To prove the correctness of **Greedy** Algorithm and show that it is optimal, we need the following observation.

**Observation 6** For every $1 \le i < j \le n$ such that $\{v_i, v_j\} \in E$, then $\{v_i, v_j\}$ separates $\{v_{i+1}, \dots, v_{j-1}\}$ from $\{v_1, v_n\} \setminus \{v_i, v_j\}$.

**Theorem 3** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{out} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected and either $x = y$ or $y \in x$ or $x \in y$. Then, an optimal $\{x, y\}$-path-decomposition of $G$ can be computed in linear time (in time $O(|E|)$). Moreover, if $x = y$ or $y \in x$, then $\mathbf{p}\ell(G, x, y) = \max_{v \in V, u \in x} \text{dist}(v, u)$.
<figure><img src="image_5.png" /><figcaption>Figure 2: Example of an embedded outerplanar graph $G$ (top) with $x \in E_{\text{out}}$ (in bold). The ordering obtained by following the outer-face clockwise is $O = (v_1, \dots, v_{13})$ with $x = \{v_1, v_{13}\}$. Then, $D(O) = (X_1 = \{v_1\}, \{v_1, v_2\}, \{v_1, v_2\}, \{v_1, v_2, v_3\}, \{v_1, v_2, v_3\}, \{v_1, v_2, v_3, v_4\}, \{v_1, v_2, v_4\}, \{v_1, v_2, v_4, v_5\}, \{v_1, v_5\}, \{v_1, v_5, v_6\}, \{v_1, v_5, v_6\}, \{v_1, v_5, v_6, v_7\}, \{v_1, v_5, v_7\}, X_{14} = \{v_1, v_5, v_7, v_8\}, \{v_1, v_5, v_7, v_8\}, \{v_1, v_5, v_7, v_8, v_9\}, \{v_1, v_5\}, \{v_1, v_5, v_{10}\}, \{v_1, v_{10}\}, \{v_1, v_{10}, v_{11}\}, \{v_1, v_{10}, v_{11}\}, \{v_1, v_{10}, v_{11}, v_{12}\}, \{v_1, v_{10}, v_{11}\}, \{v_1, v_{10}, v_{11}, v_{13}\})$. Hence, $\text{Greedy}(G) = D(O) \cup \{v_{13}\}$ and its length equals 4 (reached, e.g., in bag $X_{14} \cup \{v_{13}\}$ where $v_8$ is introduced).</figcaption></figure>

At the bottom, the reduced $\{x, x\}$-path-decomposition obtained from $\text{Greedy}(G)$ is depicted.

**Proof.** First, let us consider the case $y = x$. We show that $\text{Greedy}(G)$ provides an optimal $\{x, x\}$-path-decomposition. Trivially, its time-complexity is linear. Next, if $\text{p}\ell(G, x, x) = 1$, by definition of Greedy and by Observation 5, $\text{Greedy}(G)$ is an $\{x, x\}$-path-decomposition of length one. Let us assume that $\text{p}\ell(G, x, x) > 1$ and let $O = (v_1, \dots, v_n)$ be the ordering of $V$ following the outer-face of the chosen outerplanar embedding. By Observation 1, $\text{Greedy}(G)$ is a path-decomposition and, by construction, $x$ belongs to every bag. It only remains to prove that it is optimal, i.e., it has length $\text{p}\ell(G, x, x)$.

First, note that $\text{p}\ell(G, x, x) \ge \max_{v \in V, u \in x} \text{dist}(v, u) := k$ since $x$ belongs to all bags. We will prove that $\ell(\text{Greedy}(G)) \le k$ and so $\ell(\text{Greedy}(G)) = \text{p}\ell(G, x, x)$. Let $\text{Greedy}(G) = (X_1, \dots, X_q)$. Recall that, by definition of $D(O)$, for every $2 \le i < n$, $X_{2i-1} \subseteq X_{2i-2}$ and $X_{2i-2}$ is the first bag in which $v_i$ appears.

For purpose of contradiction, let us assume that $\ell(X_{2i-2}) > k$ and let $v_a, v_b \in X_{2i-2}$, with $1 < a < b \le i$, such that $\text{dist}(v_a, v_b) > k$. Note that, by definition of $k$, we have $v_a, v_b \in X_{2i-2} \setminus x$. Since $v_a \in X_{2i-2}$, there exists $i \le j \le n$ such that $v_a \in N(v_j)$. If $b = j$, then $\text{dist}(v_a, v_b) = 1$, a contradiction. Hence, $a < b < j$ and by Observation 6, $\{v_a, v_j\}$ separates $v_b$ from $x \setminus \{v_a, v_j\}$. Hence, any shortest path $P$ from $v_b$ to $x \setminus \{v_j\}$ intersects $\{v_a, v_j\}$. If $v_a \in V(P)$, we get that $\text{dist}(v_a, v_b) \le |E(P)| \le \max_{\alpha \in x} \text{dist}(v_b, \alpha) \le k$. Otherwise, if $v_j \in V(P)$, since $v_j \notin x \setminus \{v_j\}$ we have that $\text{dist}(v_b, v_j) < |E(P)| \le k$, and
so we get that $dist(v_a, v_b) \le dist(v_b, v_j) + 1 \le k$. In both cases, we get a contradiction.

Hence, $\ell(\text{Greedy}(G)) \le k$, and so $\ell(\text{Greedy}(G)) = p\ell(G, x, x)$.

Finally, let us assume that $x \ne y$, i.e., let $x = \{u, v\}$ and $y = v$ (the case when $x \in y$ is symmetric). An optimal $\{x, y\}$-path-decomposition can be computed from a $\{x, x\}$-path-decomposition (which can be computed in linear time by previous part of the proof) as follows. Let $(X_1, \dots, X_q)$ be an optimal $\{x, x\}$-path-decomposition and then $u$ is removed from $X_h$ for every $i < h \le q$ where $i$ is the smallest integer such that $N(u) \subseteq \bigcup_{1 \le j \le i} X_j$. The obtained decomposition is an $\{x, y\}$-path-decomposition and the fact that it is optimal follows the same arguments as above. ■

## 4.2 Case when $x$ and $y$ are “around” the same face

In this section, we consider the last remaining case which is much more technical than previous ones. Namely, let $G = (V, E)$ be a $n$-node connected simple outerplanar graph and $x, y \in E_{out} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \ne y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$ (i.e., they are not separated by an edge or a vertex).

In this setting, we first show that there always exists an almost optimal $\{x, y\}$-path-decomposition satisfying specific properties (first, *contiguous*, then *g-contiguous* (Section 4.2.2)) and finally *LtR g-contiguous* (Section 4.2.3), see formal definitions below). Intuitively, contiguous means that the components of $G \setminus F$ are included in the path-decomposition “one by one”; g-contiguous means that, in addition, the decomposition of each component is obtained using the algorithm *Greedy* of Section 4.1.3; and, finally, *LtR* means that the components are included in the path-decomposition “from left to right”, meaning the components closer to $x$ before the components closer to $y$. Then, a dynamic programming algorithm to compute such an almost optimal $\{x, y\}$-path-decomposition is presented (Section 4.2.4). We first need further notation presented in Section 4.2.1.

### 4.2.1 Notation

Let $x = \{x_1, x_2\}$ and $y = \{y_1, y_2\}$ (to simplify the presentation, we assume that $x, y \in E_{out}$. If $x \in V$ (resp., $y \in V$), it is sufficient to set $x_1 = x_2$ (resp., $y_1 = y_2$)). Let $F$ (the internal face containing $x$ and $y$) consists of two internally disjoint paths $P_{up}$ between $x_1$ and $y_1$ and $P_{down}$ between $x_2$ and $y_2$ (if $x$ and $y$ are edges, they may share one vertex, in which case, we assume that $x_2 = y_2$ and $P_{down}$ is reduced to $x_2$). In what follows, to simplify the notation, we write $F$ instead of $V(F)$.

Let $C$ be the set of connected components of $G \setminus F$. Let $C_{up}$ (resp., $C_{down}$) be the set of connected components $C$ of $G \setminus F$ such that $N(C) \subseteq V(P_{up})$ (resp., $N(C) \subseteq V(P_{down})$). For every $C \in C_{up} \cup C_{down}$, let $\bar{C} = C \cup N(C)$ and let $s_C = N(C)$. Note that, since $G$ is an outerplanar graph and $F$ is a face, then $s_C$ is either an edge or one vertex of $F$. We set $s_C = \{l_C, r_C\}$ with $l_C$ closer to $x$ and $r_C$ closer to $y$ (abusing the notation, if $s_C$ is a vertex, then $l_C = r_C$). See an illustration in Figure 3.

**Lemma 11** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{out} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \ne y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$.
<figure><img src="image_6.png" /><figcaption>Figure 3: Example of an outerplanar graph $G$ where $x = \{x_1, x_2\}$ and $y = \{y_1, y_2\}$ belong to a same internal face $F$. The paths $P_{up}$ and $P_{down}$ are depicted by dotted lines in blue and red respectively. There are four components in $G\setminus F$: $C_1, C_2 \in C_{up}$ and $C_3, C_4 \in C_{down}$ (each component is comprised in a dotted circle). The component $C_1$ is convenient with $M_{C_1} = V(C_1)$ and $h_{C_1}^*$ uniquely defined (the only vertex at distance 2 from both $l_{C_1}$ and $r_{C_1}$). The component $C_2$ is not convenient with $M_{C_2} = \{a, b\}$, and so $h_{C_2}^*$ is any of $a$ or $b$. $M_{C_3}$ is convenient and consists of $h_{C_3}^*$ and its left neighbour. Finally, $C_4$ is convenient with $l_{C_4} = r_{C_4} = r_{C_3}$. Recall that, for every $1 \le i \le 4$, $\bar{C}_i = C_i \cup s_{C_i}$.</figcaption></figure>

If $\mathfrak{pl}(G, x, y) \le k$, then there exists an $\{x, y\}$-path-decomposition $D' = (X_1, \dots, X_p)$ of $G$ with length at most $k$ such that, for every $C \in \mathcal{C}$ and every $i \le p$, if $X_i \cap C \ne \emptyset$, then $s_C \in X_i$ (or $s_C \subseteq X_i$ if $s_C$ is an edge).

**Proof.** Given a path-decomposition $(X_1, \dots, X_p)$ of $G$ and a component $C \in \mathcal{C}$, we say that $C$ satisfies Property (*) if, for every $i \le p$ such that $X_i \cap C \ne \emptyset$, then $s_C \in X_i$.

Consider an $\{x, y\}$-path-decomposition $D' = (X_1, \dots, X_p)$ of $G$ with length at most $k$ that maximizes the number of components $C \in \mathcal{C}$ that satisfy the property (*).

For purpose of contradiction, let us assume that there exists $C \in \mathcal{C}$ that does not satisfy the property (*). W.l.o.g., assume that $C \in C_{up}$. Let $1 \le i \le j \le p$ be the smallest (largest respectively) integer such that $C \cap X_i \ne \emptyset$ ($C \cap X_j \ne \emptyset$, resp.). Note that, for every $i \le h \le j$, $X_h \cap V(P_{down}) \ne \emptyset$, and, moreover, for every vertices $u \in s_C$, $v \in C$ and $w \in V(P_{down})$, $\text{dist}(u, w) \le \text{dist}(v, w)$ and $\text{dist}(v, u) \le \text{dist}(v, w)$.

Then, $(X_1, \dots, X_{i-1}, X_i \cup s_C, \dots, X_j \cup s_C, X_{j+1}, \dots, X_p)$ is an $\{x, y\}$-path-decomposition of $G$ with length at most $k$, contradicting the maximality of $D'$. ■

Let $C$ be a component of $G \setminus F$.

* If $s_C$ is a vertex, let $d_C = \max_{v \in \bar{C}} \text{dist}(v, s_C)$ and let $h_C^* \in \bar{C}$ be any vertex such that $\text{dist}(h_C^*, s_C) = d_C$.
* If $s_C$ is an edge, let $s_C = \{l_C, r_C\}$ and let $d_C = \max_{v \in \bar{C}} \max\{\text{dist}(v, r_C), \text{dist}(v, l_C)\}$ and let $M_C = \{v \in \bar{C} \mid \max\{\text{dist}(v, r_C), \text{dist}(v, l_C)\} = d_C\}$. Note that, for every $v \in \bar{C}$, $\text{dist}(v, l_C) - 1 \le \text{dist}(v, r_C) \le \text{dist}(v, l_C) + 1$. If there exists $v \in M_C$ such that $\text{dist}(v, r_C) = \text{dist}(v, l_C) = d_C$, then let $h_C^*$ be such a vertex. Otherwise, let $h_C^*$ be any vertex of $M_C$.

If $s_C$ is a vertex or if there exists a vertex $v \in M_C$ with $\text{dist}(v, r_C) = \text{dist}(v, l_C) = d_C$, we say that $C$ is a *convenient* component. See an illustration in Figure 3.

**Observation 7** Let $C$ be a connected component of $G \setminus F$ and let $v \in C$ and $u \in G \setminus C$. If $C$ is convenient or $v \notin M_C$, then $\text{dist}(v, u) \le \text{dist}(h_C^*, u)$. Otherwise, $\text{dist}(v, u) \le \text{dist}(h_C^*, u) + 1$.

### 4.2.2 Toward $g$-contiguous decompositions

Let $D = (X_1, \dots, X_p)$ be any $\{x, y\}$-path-decomposition of $G$ and let $C \in \mathcal{C}$. The component $C$ is said to be *contiguous* (with respect to $D$) if there exist $1 \le a_C \le b_C \le p$ such that:

1. $C \cap X_i \ne \emptyset$ if and only if $a_C \le i \le b_C$, and $s_C \subseteq X_i$ for all $a_C \le i \le b_C$, and

2. there exists $R_C \subseteq F$ such that $X_i \setminus C = R_C$ for every $a_C \le i \le b_C$.

Intuitively, $C$ is contiguous w.r.t. $D$ if, once a vertex of $C$ has been introduced in $D$, no vertex of $G \setminus C$ can be introduced in $D$ before all vertices of $C$ have been introduced.

A path-decomposition $D$ is *contiguous* if every component of $G \setminus F$ is contiguous w.r.t. $D$. See Figure 4 for an illustration.

In what follows, we show that there always exists an optimal (or almost optimal) $\{x, y\}$-path-decomposition of $G$ which is contiguous. Let us start with the following constrained (we assume that all components of $G \setminus F$ are convenient) but more favorable case (and easier to prove).

**Theorem 4** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \ne y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$. Moreover, let us assume that all components of $G \setminus F$ are convenient.

If $\text{pl}(G, x, y) \le k$, then there exists a contiguous $\{x, y\}$-path-decomposition $D'$ of $G$ with length at most $k$.

**Proof.** Given any $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ with length at most $k$, let $Q(D) \subseteq C$ be a set (possibly empty) of components $C$ of $\mathcal{C}$ such that there exist $1 \le a_C \le b_C \le p$ such that:

1. $C \cap X_i \ne \emptyset$ if and only if $a_C \le i \le b_C$, and $s_C \subseteq X_j$ for all $a_C \le j \le b_C$, and

2. there exists $R_C \subseteq F \cup \bigcup_{C' \notin Q(D)} C'$ such that, for every $a_C \le i \le b_C$, $X_i \setminus C = R_C$.
<figure><img src="image_7.png" /><figcaption>Figure 4: On top, an embedded outerplanar graph $G$ with $x, y \in E_{out}$ belonging to a same internal face $F$ and such that $G \setminus F$ has four components $C_1, \dots, C_4$. Colours are only there to help the reading.</figcaption></figure>

Middle: a non-contiguous $\{x, y\}$-path-decomposition $D_1 = (X_1, \dots, X_{10})$ of $G$. Component $C_3$ (with $a_{C_3} = 1$ and $b_{C_3} = 2$) is not contiguous because $s_{C_3} \not\subseteq X_{a_{C_3}}$. Component $C_2$ is not contiguous because vertices of $C_4$ are included between $a_{C_2} = 3$ and $b_{C_2} = 6$. Component $C_1$ is not contiguous because $y_1 \in F$ is included between $a_{C_1} = 7$ and $b_{C_1} = 9$. Component $C_4$ is contiguous.

At the bottom: a contiguous $\{x, y\}$-path-decomposition $D_2 = (X_1, \dots, X_8)$. It is not g-contiguous because the path-decomposition $(X_5 \cap \bar{C}_2, X_6 \cap \bar{C}_2)$ of $\bar{C}_2$ is not the result of an execution of **Greedy**($\bar{C}_2$). Finally, it is not an *LtR*-decomposition because the component $C_4$ appears before the component $C_3$.
Let us consider an {$x, y$}-path-decomposition $D' = (X_1, \dots, X_p)$ of $G$ with length at most $k$, and that maximizes $|Q(D')|$. If $Q(D') = \mathcal{C}$, then $D'$ is the desired path-decomposition, i.e., $D'$ is contiguous.

For purpose of contradiction, let us assume that $\mathcal{C} \setminus Q(D') \neq \emptyset$. Let $C \in \mathcal{C} \setminus Q(D')$ and let $1 \le i \le p$ be the smallest integer such that $h_C^* \in X_i$. Note that, by Lemma 11, we can ensure that $s_C \subseteq X_i$. Note also that, there is no $C' \in Q(D')$ such that $a_{C'} < i \le b_{C'}$ by the second property above.

Let $Y = (D' \cap C) \cup (s_C \cup (X_{i-1} \cap X_i) \setminus C)$. By Observation 7, and the fact that $C$ is convenient, $\ell(Y) \le k$.

Therefore, $D'' = (X_1 \setminus C, \dots, X_{i-1} \setminus C) \odot Y \odot (X_i \setminus C, \dots, X_p \setminus C)$ is an {$x, y$}-path-decomposition of $G$, with length at most $k$, and such that $Q(D') \cup \{C\} \subseteq Q(D'')$. This contradicts the maximality of $|Q(D')|$.

Next, we consider the case when not all components of $G \setminus F$ are convenient. We show that imposing the path-decomposition to be contiguous may increase the length of the path-decomposition by at most one. Later, we show that this increase cannot be avoided.

**Theorem 5** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \neq y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$.

If $\mathbf{p}\ell(G, x, y) \le k$, then there exists a contiguous {$x, y$}-path-decomposition $D'$ of $G$ with length at most $k+1$.

**Proof.** Let $D = (X_1, \dots, X_p)$ be any {$x, y$}-path-decomposition of $G$ with length at most $k+1$, such that, for every $1 \le i \le p$, every $C \in \mathcal{C}$ and every $u, v \in C \cap X_i$, we have that $\text{dist}(u, v) \le k$ (Property $(*)$). Note that any path-decomposition of length at most $k$ trivially satisfies Property $(*)$ and, since $\mathbf{p}\ell(G) \le k$, there exist path-decompositions with Property $(*)$.

Let $Q(D) \subseteq \mathcal{C}$ be a set of components $C$ of $\mathcal{C}$ such that there exist $1 \le a_C \le b_C \le p$ such that:

1. $C \cap X_i \neq \emptyset$ if and only if $a_C \le i \le b_C$, and $s_C \subseteq X_i$ for all $a_C \le i \le b_C$, and

2. there exists $R_C \subseteq F \cup \bigcup_{C' \notin Q(D)} C'$ such that, for every $a_C \le i \le b_C$, $X_i \setminus C = R_C$, and

3. for every $1 \le j \le p$ such that there exists no $C \in Q(D)$ with $a_C \le j \le b_C$, then $\ell(X_j) \le k$. Moreover, if there exist $C, C' \in Q(D)$ with $b_C = j = a_{C'} - 1$, then $\ell(X_j \cap X_{j+1}) \le k$.

Let us consider an {$x, y$}-path-decomposition $D' = (X_1, \dots, X_p)$ of $G$ with length at most $k+1$ and satisfying Property $(*)$, and that maximizes $|Q(D')|$. If $Q(D') = \mathcal{C}$, then $D'$ satisfies the requirements of the theorem.

For purpose of contradiction, let us assume that $\mathcal{C} \setminus Q(D') \neq \emptyset$. Let $C \in \mathcal{C} \setminus Q(D')$ and let $1 \le i \le p$ be the smallest integer such that $h_C^* \in X_i$. Note that, by Lemma 11, we may assume that $s_C \subseteq X_i$. Note also that, there is no $C' \in Q(D')$ such that $a_{C'} < i \le b_{C'}$ by the second property of the definition of $Q(D')$.
<figure><img src="image_8.png" /><figcaption>Figure 5: Example of a graph $G$ and $x, y \in E_{\text{out}}$ such that every contiguous $\{x, y\}$-path-decomposition of $G$ has length at least $\mathbf{p}\ell(G, x, y) + 1$. Each line with weight $w$ represents a path of length $w$ (a line without weight is an edge, i.e., of length one).</figcaption></figure>

Let $Y = (D' \cap C) \cup (s_C \cup (X_{i-1} \cap X_i) \setminus C)$. By Property $(*)$, Observation 7 and the third item above, $\ell(Y) \le k+1$ (if $C$ is convenient, we even have $\ell(Y) \le k$).

Therefore, $D'' = (X_1 \setminus C, \dots, X_{i-1} \setminus C) \odot Y \odot (X_i \setminus C, \dots, X_p \setminus C)$ is an $\{x, y\}$-path-decomposition of $G$, with length at most $k+1$ and satisfying Property $(*)$, and such that $Q(D') \cup \{C\} \subseteq Q(D'')$. This contradicts the maximality of $|Q(D')|$. ■

Unfortunately, the previous theorem cannot be improved since there are 2-connected outerplanar graphs $G$ and $x, y \in E_{\text{out}}$, such that every contiguous $\{x, y\}$-path-decomposition has length at least $\mathbf{p}\ell(G, x, y) + 1$.

**Lemma 12** *There exists a 2-connected outerplanar graph $G$ and $x, y \in E_{\text{out}}$ such that every contiguous $\{x, y\}$-path-decomposition of $G$ has length at least $\mathbf{p}\ell(G, x, y) + 1$.*

**Proof.** Let $G$ be the graph depicted in Figure 5. Let $C$ be the unique component of $G\setminus F$. Let $M, L$ and $R$ be the set of vertices of the corresponding faces. Let us first describe an $\{x, y\}$-path-decomposition $D$ of $G$ with length 10. Let $X_1 = x, X_2 = L \cup M \cup L'$ where $L'$ is the $(x_2, r_c)$-path in $F$ not containing $y_1$ and $y_2$. Let $X_3 = M \cup V(P_{\text{down}})$ where $P_{\text{down}}$ is the $(x_2, y_2)$-path in $F$ not containing $x_1$ and $y_1$. Let $X_4 = M \cup R \cup R'$ where $R'$ is the $(y_2, l_c)$-path in $F$ not containing $x_1$ and $x_2$. Finally, let $X_5 = y$. Note that $D = (X_1, \dots, X_5)$ is an $\{x, y\}$-path-decomposition of length 10. Moreover, $D$ is not contiguous since for $X_2$ and $X_4$ contains both vertices from $C$ but $X_2\setminus C \neq X_4\setminus C$.

Now, let $D = (X_1, \dots, X_p)$ be any contiguous $\{x, y\}$-path-decomposition of $G$. Let $1 \le i, j \le p$ such that $r \in X_i$ and $l \in X_j$. By definition of being contiguous, $X_i \cap V(P_{\text{down}}) = X_j \cap V(P_{\text{down}})$. Since every vertex of $P_{\text{down}}$ is at distance at least 11 from $r$ or $l$, then $\ell(D) \ge 11 > \mathbf{p}\ell(G)$. ■

A contiguous $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ is said to be *g-contiguous* if, for every $C \in \mathcal{C}$, $(D_{a_C} \cap \bar{C}, \dots, D_{b_C} \cap \bar{C})^1$ is an optimal greedy path-decomposition of $G[\bar{C}] = G[C \cup s_C]$ based on $s_C$ (see Section 4.1.3).

**Theorem 6** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \neq y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$.

<footnote n="1">¹Recall the definitions of $a_C$ and $b_C$ from the definition of $D$ being contiguous.</footnote>
If $\mathbf{p}\ell(G, x, y) \le k$, then there exists a $g$-contiguous $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ with length at most $k+1$. Moreover, for every $C \in \mathcal{C}$ and $a_C \le i \le b_C$, $\ell(X_i) = \ell(D)$ only if $h_C^* \in X_i$ for some $h_C^* \in \mathcal{M}_C$.

**Proof.** By Theorem 5, there exists a contiguous $\{x, y\}$-path-decomposition $D' = (X_1, \dots, X_p)$ of $G$ with length at most $k+1$.

Iteratively, for every component $C \in \mathcal{C}$, replace $D'$ with $(X_1, \dots, X_{a_C-1}) \odot \mathcal{G}(C) \cup (X_{a_C-1} \cap X_{b_C+1}) \odot (X_{b_C+1}, \dots, X_p)$ where $\mathcal{G}(C)$ is an optimal greedy path-decomposition of $G[\bar{C}] = G[C \cup s_C]$ based on $s_C$. This remains a contiguous $\{x, y\}$-path-decomposition of $G$ since, for every $a_C \le i \le b_C$, $s_C \in X_i$ and $X_i \setminus C \subseteq F$.

Moreover, by construction of $D'$ (see the proof of Theorem 5), two vertices $u$ and $v$ in a bag $X_i$ ($a_C \le i \le b_C$ for some $C \in \mathcal{C}$) may be at distance $\ell(D)$ only if $u \in C$ and $v \in F$. Therefore, the result holds (including the last statement) by definition of greedy path-decomposition and by Observation 7. ■

### 4.2.3 Toward left-to-right $g$-contiguous decompositions

Recall that we are considering a $n$-node connected simple outerplanar graph $G = (V, E)$ and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \neq y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$.

Let $x = \{x_1, x_2\}$ if $x$ is an edge (or $x = x_1 = x_2$ if $x$ is a vertex) and let $y_1, y_2 \in V$ be defined similarly for $y$. Let $P_{\text{up}} = (x_1 = u_1, \dots, u_t = y_1)$ and $P_{\text{down}} = (x_2 = d_1, \dots, d_s = y_2)$ be the two internally disjoint paths whose union consists of all vertices of the face $F$. Note that, it may be possible that $x_1 = y_1$ or $x_2 = y_2$ but not both (in what follows, we assume that $x_1 \neq y_1$).

For every $C \in \mathcal{C}_{\text{up}}$ (i.e., such that $s_C \in V(P_{\text{up}})$ or $s_C \subseteq V(P_{\text{up}})$), recall that $l_C$ (resp., $r_C$) is the vertex of $s_C$ that is closest (resp., furthest) to $x_1$ in $P_{\text{up}}$ (or $l_C = r_C = s_C$ if $s_C$ is a vertex). Similarly, for every $C \in \mathcal{C}_{\text{down}}$ (i.e., such that $s_C \in V(P_{\text{down}})$ or $s_C \subseteq V(P_{\text{down}})$), $l_C$ (resp., $r_C$) is the vertex of $s_C$ that is closest (resp., furthest) to $x_2$ in $P_{\text{down}}$ (or $l_C = r_C = s_C$ if $s_C$ is a vertex).

An edge $e \in E(F) \setminus \{x, y\}$ is said to be *trivial* if there does not exist $C \in \mathcal{C}$ such that $e = s_C$ (note that an end of $e$ may be a cut vertex, but there is no $C \in \mathcal{C}$ with $N(C) = e$). While trivial edges are not related to any component of $G \setminus F$, we need to include them in the analysis that follows. To unify the notation, let $\bar{C} = \{\bar{C} = C \cup s_C \mid C \in \mathcal{C}\} \cup \{e \in E(F) \setminus \{x, y\} \mid e \text{ is a trivial edge}\}$. Intuitively, every trivial edge $e \in E(F) \setminus \{x, y\}$ may be seen as $e = s_C$ for some dummy empty component $C = \emptyset$. Similarly, let $\bar{C}_{\text{up}} = \{\bar{C} = C \cup s_C \mid C \in \mathcal{C}_{\text{up}}\} \cup \{e \in E(P_{\text{up}}) \mid e \text{ is a trivial edge}\}$ and $\bar{C}_{\text{down}} = \{\bar{C} = C \cup s_C \mid C \in \mathcal{C}_{\text{down}}\} \cup \{e \in E(P_{\text{down}}) \mid e \text{ is a trivial edge}\}$. Note that $\bar{C} = \bar{C}_{\text{up}} \cup \bar{C}_{\text{down}}$.

Let $\mathcal{O}_{\text{up}} = (C_1^u, \dots, C_{s'}^u)$ be any ordering of $\bar{C}_{\text{up}}$ such that, if $l_{C_i^u}$ is strictly closer to $x_1$ in $P_{\text{up}}$ than $l_{C_j^u}$ and/or if $r_{C_i^u}$ is strictly closer to $x_1$ in $P_{\text{up}}$ than $r_{C_j^u}$, then $i < j$. Similarly, let $\mathcal{O}_{\text{down}} = (C_1^d, \dots, C_{t'}^d)$ be any ordering of $\bar{C}_{\text{down}}$ such that, if $l_{C_i^d}$ is strictly closer to $x_2$ in $P_{\text{down}}$ than $l_{C_j^d}$ and/or if $r_{C_i^d}$ is strictly closer to $x_1$ in $P_{\text{down}}$ than $r_{C_j^d}$, then $i < j$. Intuitively, we order the components of $\mathcal{C}_{\text{up}}$ and the trivial edges of $P_{\text{up}}$ from $x_1$ to $y_1$ (resp., of $\mathcal{C}_{\text{down}}$ and the trivial edges of $P_{\text{down}}$ from $x_2$ to $y_2$), from “left to right” (“from $x$ to $y$”). Note that for every two components $C, C' \in \mathcal{C}$ such that $s_C = s_{C'} \in V$, the
<figure><img src="image_9.png" /><figcaption>Figure 6: Notation of Section 4.2.3.</figcaption></figure>

relative order between $C$ and $C'$ in $O_{up}$ (resp., in $O_{down}$ if $s_C \in V(P_{down})$) is arbitrary (but all connected components $C'$ with $s_C = s_{C'}$ are consecutive in $O_{up}$ (resp., in $O_{down}$)).

In this section, we only consider $g$-contiguous $\{x, y\}$-path-decompositions $D = (X_1, \dots, X_p)$ of $G$. That is, for every $C \in \mathcal{C}$, there exist $1 \le a_C \le b_C \le p$, and an interval $I_C = [a_C, b_C]$ such that $X_i \cap C \ne \emptyset$ if and only if $i \in I_C$, $s_C \in X_i$ for all $i \in I_C$ and $X_i \setminus C \subseteq F$ for all $i \in I_C$. In particular, $I_C \cap I_{C'} = \emptyset$ for all distinct $C, C' \in \mathcal{C}$. We say that $C$ appears in $D$ in the bag $X_{a_C}$. Moreover, $(X_{a_C} \cap \bar{C}, \dots, X_{b_C} \cap \bar{C})$ is a greedy path-decomposition of $G[\bar{C}]$ based on $s_C$. Recall also that we may assume that the property of the last statement in Theorem 6 holds.

By definition, $D$ induces a total order $O_D = (\bar{C}_1, \dots, \bar{C}_b)$ on $\bar{C}$ such that, for any $1 \le i < j \le b$, $\bar{C}_i$ appears in $D$ before $\bar{C}_j$ (i.e., $b_{\bar{C}_i} < a_{\bar{C}_j}$). We aim at considering such $g$-contiguous $\{x, y\}$-path-decompositions $D$ such that the total orders $O_D$ they induce satisfy some extra property defined below.

Let $H = H^1 \cup H^2$ be a ground set with $H^1 \cap H^2 = \emptyset$. Let $O = (H_1, \dots, H_q)$ be a total ordering on $H$, and let $O^i$ be a total ordering of $H^i$ for $i \in \{1, 2\}$. A prefix $\mathcal{P} = (H_1, \dots, H_{q'})$ ($q' \le q$) of $H$ is compatible with $O^i$ if $\mathcal{P} \cap H^i$ is a prefix of $O^i$ for $i \in \{1, 2\}$. If $q' = q$, then $O$ is said to be compatible with $O^1$ and $O^2$.

Roughly, a contiguous $\{x, y\}$-path-decompositions $D$ of $G$ is said to be *LtR* (left to right) if $O_D$ is compatible with $O_{up}$ and $O_{down}$. More precisely,

**Definition 1** A contiguous $\{x, y\}$-path-decompositions $D = (X_1, \dots, X_p)$ of $G$ is LtR if and only if:

1. for every $C_i^u, C_j^u \in O_{up}$ (resp., $C_i^d, C_j^d \in O_{down}$) with $i < j$, $b_{C_i^u} < a_{C_j^u}$ (resp., with $b_{C_i^d} < a_{C_j^d}$) and, moreover,

2. for every $C \in \bar{C}_{up}$ (resp., $\bar{C}_{down}$), and $i \in I_C$, $X_i \cap F = \{l_C, r_C, f_C\}$ where $f_C$ is one vertex of $V(P_{down})$ (resp., of $V(P_{up})$).

In what follows, we will iteratively transform a given $g$-contiguous $\{x, y\}$-path-decomposition of $G$ into different path-decompositions. While, during these transformations, the obtained path-decomposition will always remain a $g$-contiguous $\{x, y\}$-path-decomposition of $G$, its length may be increased temporarily. To deal with this difficulty, let us define the *weak length*, denoted by $wl(D)$, of an $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of an outerplanar graph $G$ (where $x$ and $y$ are outer edges of a same face of $G$). The weak
length, denoted by $w\ell(X_i)$, of a bag $X_i$ ($1 \le i \le p$) is $\max_{u \in X_i, v \in X_i \cap Y} \text{dist}(u, v)$ where $Y = V(P_{up})$ (resp., $Y = V(P_{down})$) if $a_C \le i \le b_C$ for a component $\bar{C} \in \bar{C}_{down}$ (resp., $C \in \bar{C}_{up}$). Then, $w\ell(D) = \max_{i \le p} w\ell(X_i)$.

**Lemma 13** Let $D$ be a $\text{LtR}$ $g$-contiguous $\{x, y\}$-path-decomposition of $G$ of weak length $k$. Then, $\ell(D) \le k$.

**Proof.** For purpose of contradiction, let $B$ be a bag of $D$ such that $\ell(B) > k$ and $\ell(B)$ is maximum. Let $C$ be the component of $G \setminus F$ such that $B \subseteq \bar{C} \cup \{f_C\}$ (it exists because $D$ is $\text{LtR}$). Let $u, v \in B$ such that $\text{dist}(u, v) > k$. Because $D$ has weak length $k$, then $u, v \in \bar{C}$ (i.e., $f_C \notin \{u, v\}$). Then, because $D$ is $g$-contiguous, $D \cap \bar{C}$ is an optimal greedy $(s_C, s_C)$-path-decomposition and $\ell(D \cap \bar{C}) = \max_{v \in C, \alpha \in s_C} \text{dist}(v, \alpha) = \max_{\alpha \in s_C} \text{dist}(h_C^*, \alpha)$ for some $h_C^* \in \mathcal{M}_C$ (by Theorem 3 and definition of $h_C^*$). Hence, $\text{dist}(u, v) \le \max_{\alpha \in s_C} \text{dist}(h_C^*, \alpha) \le d(h_C^*, f_C) \le w\ell(D) \le k$, a contradiction. ■

The next theorem roughly says that, from a $g$-contiguous $\{x, y\}$-path-decomposition, we can add the property that it is $\text{LtR}$ without increasing the length.

**Theorem 7** Let $G = (V, E)$ be a connected simple outerplanar graph and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \ne y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face $F$ of $G$.

Let us assume that there exists a $g$-contiguous $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ with length $k$ and such that, for every $C \in \mathcal{C}$ and $a_C \le i \le b_C$, $\ell(X_i) = k$ only if $h_C^* \in X_i$ for some $h_C^* \in \mathcal{M}_C$.

Then, there exists a $\text{LtR}$ $g$-contiguous $\{x, y\}$-path-decomposition of $G$ with length at most $k$.

**Proof.** Let $D = (X_1, \dots, X_p)$ be a $g$-contiguous $\{x, y\}$-path-decomposition of $G$ with weak length at most $k$. We say that $D$ satisfies Property (*) if, for every $C \in \mathcal{C}$ and $a_C \le i \le b_C$, $w\ell(X_i) = k$ only if $h_C^* \in X_i$ for some $h_C^* \in \mathcal{M}_C$.

Recall that $\mathcal{O}_{up}$ (resp., $\mathcal{O}_{down}$) are not uniquely defined in the sense that the order between two components $C, C' \in \mathcal{C}_{up}$ (resp., $C, C' \in \mathcal{C}_{down}$) with $s_C = s_{C'} \in V$ is arbitrary (but all such components are consecutive in $\mathcal{O}_{up}$ (resp., $\mathcal{O}_{down}$)).

Let $D = (X_1, \dots, X_p)$ be $g$-contiguous $\{x, y\}$-path-decomposition of $G$ with weak length at most $k$ satisfying Property (*). Such a decomposition exists since a decomposition of length $k$ is of weak length at most $k$ and satisfies Property (*). Let $\mathcal{O}_{up}$ and $\mathcal{O}_{down}$ be orderings of $\bar{C}_{up}$ and $\bar{C}_{down}$ (as defined previously) such that $D, \mathcal{O}_{up}$ and $\mathcal{O}_{down}$ maximize $1 \le h \le p$ such that $(X_1, \dots, X_h)$ is compatible with $\mathcal{O}_{up}$ and $\mathcal{O}_{down}$.

**Claim 1** If $h = p$, then there exists a $\text{LtR}$ $g$-contiguous $\{x, y\}$-path-decomposition of $G$ with length at most $k$.

*Proof of the Claim.* We show that, if $h = p$, $D$ can be transformed into an $\text{LtR}$ $g$-contiguous $\{x, y\}$-path-decomposition as follows. Note that it only remains to ensure that $D$ also satisfies the second property of $\text{LtR}$ path-decompositions. For every $1 \le i \le p$, let $C$ be the component of $G \setminus F$ such that $X_i \setminus F \subseteq C$ (it exists by definition of being contiguous). Let us assume that $C \in \mathcal{C}_{up}$ (the case when $C \in \mathcal{C}_{down}$ is symmetric) and
<figure><img src="image_10.png" /><figcaption>Figure 7: Schematic representation of the notation introduced before Claim 2. The curves linking two adjacent vertices of the face F represent the components of $G\setminus F$. We consider a $g$-contiguous {$x, y$}-path-decomposition $D = (X_1, \dots, X_p)$ of $G$. The components on the left of $u_i$ and $d_j$ are the ones appearing in $(X_1, \dots, X_h)$ in the order $O$. Moreover, $C_1, \dots, C_q$ are the components on the right of $u_i$ and $d_i$ in the order they appear in $(X_{h+1}, \dots, X_p)$. Then, $C'_1, \dots, C'_{q'}$ are the components of $C_{up}$ on the right of $u_i$ in the order they appear, from left to right, on the face.</figcaption></figure>

let $C' \in C_{down}$ be the largest component (in $O_{down}$) that appears in $\bigcup_{j<i} X_j$. Then, let $X'_i = (X_i \cap \bar{C}) \cup \{r_{C'}\}$ (Intuitively, we remove from each bag $X_i$, the vertices of $F$ that are now useless because their neighbouring components have already been included or that are not useful yet because their neighbouring components have not been included yet). Let $C''$ be the component of $C_{down}$ just after $C'$ in $O_{down}$. By definition of the ordering, $r_{C'} \in s_{C''}$ and since $C''$ did not appear yet, then $r_{C'} \in X_i$ (because $r_{C'}$ has a neighbour in $\bar{C}'' \setminus \{r_{C'}\}$ and the corresponding edge did not appear yet in the decomposition). That is $X'_i \subseteq X_i$. Hence, $D' = (X'_1, \dots, X'_p)$ is a $\text{LtR } g$-contiguous {$x, y$}-path-decomposition of $G$ with weak length at most $k$ satisfying Property $(*)$. By Lemma 13, $D'$ has not only weak length at most $k$ but also $\ell(D') \le k$ and so, it is the desired path-decomposition. $\diamond$

Hence, for purpose of contradiction, let us assume that $h < p$.

Note that, because $D$ is a contiguous {$x, y$}-path-decomposition and because $(X_1, \dots, X_h)$ is compatible with $O_{up}$ and $O_{down}$, there exist $1 \le i \le s$ and $1 \le j \le t$ (recall that $P_{up} = (u_1, \dots, u_s)$ and $P_{down} = (d_1, \dots, d_t)$) such that $X_h \cap X_{h+1} = \{u_i, d_j\}$. Indeed, it is possible to ensure this property by using the same modification as in the proof of Claim 1 but only restricted to bags $X_1, \dots, X_h$ and by removing all vertices of $\{u_1, \dots, u_{i-1}\} \cup \{d_1, \dots, d_{j-1}\}$ from the bags $X_{h+1}, \dots, X_p$.

Let $O_D = O \odot (C_1, \dots, C_q)$ where $O$ is the prefix of $O_D$ that corresponds to the components appearing in $(X_1, \dots, X_h)$. W.l.o.g., let us assume that $C_1 \in \bar{C}_{up}$. Let $O_{up} = O' \odot (C'_1, \dots, C'_{q'})$ where $O' = O \cap \bar{C}_{up}$. By maximality of $h$, $C_1 \ne C'_1$. More precisely, $C_1 = C'_{z(D)}$ for some $1 < z(D) \le q'$. This is illustrated in Figure 7.

**Claim 2** There exists an integer $1 \le \alpha < z(D)$ and a vertex $h^*_{C'_\alpha} \in \mathcal{M}_{C'_\alpha}$ such that $\text{dist}(h^*_{C'_\alpha}, d_j) > k$.

*Proof of the Claim.* For purpose of contradiction, let us assume that, for every $1 \le \alpha < z(D)$ and for all $h^*_{C'_\alpha} \in \mathcal{M}_{C'_\alpha}$, $\text{dist}(h^*_{C'_\alpha}, d_j) \le k$.
<figure><img src="image_11.png" /><figcaption>Figure 8: Schematic example of the transformation in the proof of Claim 2. The g-contiguous {$x, y$}-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ is represented above. In this figure, for any component $C$ of $G \setminus F$, let $H_C$ denote the path-decomposition $(X_{a_C}, \dots, X_{b_C})$. Setting $C'_1 = C_r, C'_2 = C_{r'}$ and $C'_{z(D)-1} = C_{r''}$, this example assumes that $2 < r'' < r < r' \le q$. Below is the path-decomposition $D'$ obtained after transformation (whose overview is depicted by the red arrows). In the figure, we set $Y = (\bigcup_{1 \le \alpha < z(D)} \bar{C}'_\alpha) \setminus \{l_{C'_z(D)}\})$.</figcaption></figure>

Let

$$D' = (X_1, \dots, X_h) \odot ((X_{a_{C'_1}}, \dots, X_{b_{C'_1}}) \cap \bar{C}'_1) \cup \{d_j\} \odot ((X_{a_{C'_2}}, \dots, X_{b_{C'_2}}) \cap \bar{C}'_2) \cup \{d_j\} \odot \\ \dots \odot ((X_{a_{C'_z(D)-1}}, \dots, X_{b_{C'_z(D)-1}}) \cap \bar{C}'_{z(D)-1}) \cup \{d_j\} \odot ((X_{h+1}, \dots, X_p) \setminus (\bigcup_{1 \le \alpha < z(D)} \bar{C}'_\alpha) \setminus \{l_{C'_z(D)}\})).$$

Intuitively, all components that are between (in $O_{up}$) the last component of $O$ and $C_1$ are “moved” just before $C_1$ in the decomposition (in $D$ all these components were appearing after $C_1$). This transformation is illustrated in Figure 8.

Because $D$ is g-contiguous and satisfies Property ($*$), then $D'$ is a g-contiguous {$x, y$}-path-decomposition of $G$ satisfying Property ($*$). Moreover, its weak length is at most $k$. In particular, for every bag $B$ of $((X_{a_{C'_\alpha}}, \dots, X_{b_{C'_\alpha}}) \cap \bar{C}'_\alpha) \cup \{d_j\}$ for $1 \le \alpha < z(D)$, $w\ell(B) \le k$ because $D$ satisfies Property ($*$) and because, by assumption, $\text{dist}(h^*_{C'_\alpha}, d_j) \le k$.

To conclude this case, $D'$ is g-contiguous {$x, y$}-path-decomposition of $G$ with weak length at most $k$ satisfying Property ($*$) and with a larger prefix than $D$ that is compatible with $O_{up}$ and $O_{down}$, contradicting the maximality of $h$. $\diamond$

Hence, by Claim 2, we may assume that there exist an integer $1 \le \alpha < z(D)$ and a vertex $h^*_{C'_\alpha} \in \mathcal{M}_{C'_\alpha}$ such that $\text{dist}(h^*_{C'_\alpha}, d_j) > k$. Let $\alpha(D)$ be the smallest such integer $\alpha$ for the decomposition $D$. Let $1 < \alpha^*(D) \le q$ be such that $C'_{\alpha(D)} = C_{\alpha^*(D)}$.

Consider such a decomposition $D$ (still maximizing $h$) that minimizes $\alpha^*(D)$. From now on, we denote the integer $\alpha(D)$ (for this particular decomposition $D$) by $\alpha$ and $\alpha^*(D)$ is denoted by $\alpha^*$ and $z(D)$ is denoted by $z$.

Let $\beta, \gamma$ be defined such that $\alpha < \beta \le z \le \gamma \le q'$ and $[\beta, \gamma]$ is the inclusion-maximal interval (containing $z$) such that every component $C'_m$ with $m \in [\beta, \gamma]$ appears before $C_{\alpha^*}$ in $O_D$ (i.e., for every $m \in [\beta, \gamma]$, setting $m'$ such that $C'_m = C_{m'}$, then $1 \le m' < \alpha^*$).
<figure><img src="image_12.png" /><figcaption>Figure 9: Schematic representation of the notation introduced after Claim 2. The curves linking two adjacent vertices of the face F represent the components of $G \setminus F$. The component A is an example of such components in $R_\gamma$: if A appears before $C'_\alpha = C_{\alpha^*}$ in D then $A \in R_\gamma$. Similarly, the component B is an example of such components in $L_\beta$: if B appears before $C'_\alpha = C_{\alpha^*}$ in D then $B \in L_\beta$.</figcaption></figure>

Let $L_\beta$ denote the set of components $C_{w'} = C'_w$ of $\mathcal{C}$ such that $l_{C'_\beta} \in s_{C_{w'}}, w \notin [\beta, \gamma]$ and $w' \le \alpha^*$. Intuitively, $L_\beta$ is the set of the components $C$ that appear before $C_{\alpha^*}$ in D, which will not be moved, and that contains $l_{C'_\beta}$ (note that we cannot remove $l_{C'_\beta}$ from the bags of the components in $L_\beta$ without breaking properties of path-decompositions). Note that $C_{\alpha^*}$ can be in $L_\beta$. Symmetrically, let $R_\gamma$ denote the set of component $C_{w'} = C'_w$ of $\mathcal{C}$ such that $r_{C'_\gamma} \in s_{C_{w'}}, w \notin [\beta, \gamma]$ and $w' \le \alpha^*$. These notations are illustrated in Figure 9.

* First, let us assume that, $L_\beta = R_\gamma = \emptyset$. Let

$$ 
\begin{aligned}
D' = (X_1, \dots, X_h) \odot & ((X_{h+1}, \dots, X_{a_{C_{\alpha^*}}-1}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \odot \\
& ((X_{a_{C_{\alpha^*}}}, \dots, X_{b_{C_{\alpha^*}}}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \odot \\
& ((X_{h+1}, \dots, X_{a_{C_{\alpha^*}}-1}) \cap \bigcup_{\beta \le m \le \gamma} \bar{C}'_m) \cup (X_{b_{C_{\alpha^*}}} \cap F) \odot (X_{b_{C_{\alpha^*}}+1}, \dots, X_p).
\end{aligned}
$$

Intuitively, all components $C'_\beta, \dots, C'_\gamma$ (and in particular, $C_1 = C'_z$) that were appearing before $C_{\alpha^*}$ in D (but that are greater than $C_{\alpha^*}$ in $O_{up}$) are “moved” after $C_{\alpha^*}$ in D. This is illustrated in Figure 10.

**Claim 3** *D' is a g-contiguous {x, y}-path-decomposition of G with Property (*).*

*Proof of the Claim.* Note first that $D'$ is a {x, y}-path-decomposition of G. Indeed, all vertices of G appear in some bag of $D'$ and the third property of path-decompositions is clearly satisfied. Moreover, the only edges that may have disappeared have an end in $\bigcup_{\beta \le m \le \gamma} \bar{C}'_m$ and the other end in $\bigcup_{h+1 \le w \le b_{C_{\alpha^*}}} X_w$.
<figure><img src="image_13.png" /><figcaption>Figure 10: Schematic example of the transformation in the case $L_{\beta} = R_{\gamma} = \emptyset$. The $g$-contiguous $\{x, y\}$-path-decomposition $D = (X_1, \dots, X_p)$ of $G$ is represented above. In this figure, for any component $C$ of $G \setminus F$, let $H_C$ denote the path-decomposition $(X_{a_C}, \dots, X_{b_C})$. The double squares represent the path-decompositions $H_C$ for those component $C = C'_m$ with $m \in [\beta, \gamma]$. Below is the path-decomposition $D'$ obtained after transformation (whose overview is depicted by the red arrows). In the figure, we set $W = \bigcup_{\beta \le m \le \gamma} \bar{C}'_m$ and $W' = X_{b_{C_{\alpha^*}}} \cap F$.</figcaption></figure>

($\bigcup_{\beta \le m \le \gamma} \bar{C}'_m$). That is, such an edge intersects $l_{C'_\beta}$ or $r_{C'_\gamma}$ and belongs to a component $C'_b$ ($b \notin [\beta, \gamma]$) which appears, in $D$, before $C_{\alpha^*}$, i.e., such an edge must belong to a component in $L_{\beta}$ or $R_{\gamma}$ that we assumed to be empty.

Because $D$ is $g$-contiguous and satisfies Property $(*)$, then $D'$ is a $g$-contiguous $\{x, y\}$-path-decomposition of $G$ satisfying Property $(*)$. $\diamond$

It remains to prove that its weak length is at most $k$.

**Claim 4** We have $wl(D') \le k$.

*Proof of the Claim.* We will prove that every bag in $((X_{h+1} \cdots, X_{a_{C_{\alpha^*}}-1}) \cap \bigcup_{\beta \le m \le \gamma} \bar{C}'_m) \cup (X_{b_{C_{\alpha^*}}} \cap F)$ has weak length at most $k$ (those are the only bags where some vertices may be added compared with the bags of $D$). Since we are considering the weak length, we actually need to prove that, for every $v \in \bigcup_{\beta \le m \le \gamma} \bar{C}'_m$ and every $w \in X_{b_{C_{\alpha^*}}} \cap V(P_{down})$, $dist(v, w) \le k$. Actually, we will show that $dist(v, w) \le dist(h^*_{C_{\alpha^*}}, w)$. Recall that $X_{a_{C_{\alpha^*}}} \cap F = X_{b_{C_{\alpha^*}}} \cap F$ because $D$ is contiguous. Hence, $w$ belongs to every bag in $X_{a_{C_{\alpha^*}}}, \dots, X_{b_{C_{\alpha^*}}}$ and so $dist(h^*_{C_{\alpha^*}}, w) \le k$.

Note that, because every vertex of the $(d_1, d_{j-1})$-path has been removed from the bags $X_{h+1}, \dots, X_p$ of $D$, then $w$ is between $d_j$ and $y_2$ in $P_{down}$. Moreover, since $dist(h^*_{C_{\alpha^*}}, d_j) > k$ and $dist(h^*_{C_{\alpha^*}}, w) \le k$, then the shortest path between $w$ and $h^*_{C_{\alpha^*}}$ goes through $y_2$.

Let $\beta \le m \le \gamma$ such that $v \in \bar{C}'_m$ and let $h < \delta < a_{C_\alpha^*}$ be such that $v \in X_\delta$ (in $D$). Because $D$ is a path-decomposition and $d_j \in X_h$ and $w \in X_{a_{C_\alpha^*}}$, there must be a vertex $w' \in X_\delta$ which is between $d_j$ and $w$ in $P_{down}$, and so $dist(v, w') \le k$ since $D$
has weak length at most $k$. If the shortest path between $v$ and $w'$ goes through $y_2$, we get that $\text{dist}(v, w) \le \text{dist}(v, w') \le k$ and we are done. Otherwise, $w$ is strictly between $w'$ and $y_2$ (in particular $w \ne w'$) (because the shortest path between $h_{C_{\alpha*}}^*$ and $w$ goes through $y_2$, the one between $v$ and $w'$ goes through $x_2$ and $s_{C_{\alpha*}}$ is closer to $x_2$ than $s_{C'_m}$). Note also that $w'$ belongs to every bag in $X_{a_{C'_m}}, \dots, X_{b_{C'_m}}$ (since $v, w' \in X_\delta$ and $v \in V(C'_m)$ and so $a_{C'_m} \le \delta \le b_{C'_m}$) and, in particular, one of these bags contains a vertex $h_{C'_m}^*$, and so $\text{dist}(h_{C'_m}^*, w') \le k$.

To sum up, $\text{dist}(w', l_{C'_m}) + \text{dist}(l_{C'_m}, h_{C'_m}^*) = \text{dist}(h_{C'_m}^*, w') \le k < \text{dist}(h_{C_{\alpha*}}^*, d_j) \le \text{dist}(w', l_{C_{\alpha*}}) + \text{dist}(l_{C_{\alpha*}}, h_{C_{\alpha*}}^*)$ (the last inequality holds because the shortest path between $w$ and $h_{C_{\alpha*}}^*$ goes through $x_2$). Because $l_{C_{\alpha*}}$ is between $x_2$ and $l_{C'_m}$ in $P_{up}$ and the shortest path between $l_{C'_m}$ and $w'$ goes through $x_2$, we get that $\text{dist}(w', l_{C'_m}) \ge \text{dist}(w', l_{C_{\alpha*}})$ and so $\text{dist}(l_{C'_m}, h_{C'_m}^*) < \text{dist}(l_{C_{\alpha*}}, h_{C_{\alpha*}}^*)$. Finally, $k \ge \text{dist}(h_{C_{\alpha*}}^*, w) = \text{dist}(h_{C_{\alpha*}}^*, r_{C_{\alpha*}}) + \text{dist}(r_{C_{\alpha*}}, w) \ge \text{dist}(r_{C'_m}, h_{C'_m}^*) + \text{dist}(r_{C'_m}, w) = \text{dist}(h_{C'_m}^*, w)$. The last inequality comes from the fact that $r_{C'_m}$ is between $y_1$ and $r_{C_{\alpha*}}$ in $P_{up}$ and the shortest path between $l_{C'_\alpha}$ and $w$ goes through $y_1$ and $y_2$. Hence, we get that $\text{dist}(h_{C'_m}^*, w) \le k$ and so, $\text{dist}(v, w) \le k$ by Property $(*)$. $\diamond$

It remains to show that $D'$ contradicts the minimality of $\alpha^*$. Let $C$ be the component that appears in $D'$ just after $X_h$.

- First, let us assume that $C \in \mathcal{C}_{up}$.

If $C < C'_\alpha$ in $\mathcal{O}_{up}$, i.e., $C = C'_\epsilon$ for some $\epsilon = z(D') < \alpha$, then by definition of $\alpha$, we have that, for every $1 \le \alpha' < \epsilon = z(D')$ and for all $h_{C'_{\alpha'}}^* \in \mathcal{M}_{C'_{\alpha'}}$, $\text{dist}(h_{C'_{\alpha'}}^*, d_j) \le k$. That is, $D'$ corresponds to the case treated in the proof of Claim 2, i.e., all components smaller than $C$ in $\mathcal{O}_{up}$ can be moved just after $X_h$ in $D'$ (recall that all these components can be added with $d_j$ by definition of $\alpha$). This contradicts the maximality of $h$.

Otherwise, by definition of $\alpha$ (and of $d_j$), we have that $\alpha(D') = \alpha(D) = \alpha$ and then, $C_{\alpha^*(D')} = C_{\alpha^*(D)} = C'_{\alpha(D)}$. Since $C_{\alpha^*(D)}$ is “closer” from $X_h$ in $D'$ than in $D$ (since $D'$ is obtained from $D$ by moving at least $C_1$ after $C_{\alpha^*(D)}$), we get that $\alpha^*(D') < \alpha^*(D)$, contradicting the minimality of $\alpha^*(D)$.

- If $C \in \mathcal{C}_{down}$, then we repeat the whole process starting from $D'$. Either we fall in the first case (of Claim 1), which contradicts the maximality of $h$, or we have to repeat the transformation of the second case (e.g., as the one illustrated in Figure 10). This leads to a new decomposition $D''$ with the same prefix $(X_1, \dots, X_h)$ and a component $C'$ that appears just after this prefix in $D''$. If $C' \in \mathcal{C}_{down}$, then applying the above paragraph (of previous item) with $D'$ and $D''$ instead of $D$ and $D'$ leads to a contradiction. Otherwise, since the prefix (and so $d_j$) is the same, then applying the paragraph above (of previous item) for $C'$ also contradicts the minimality of $\alpha^*(D)$ (i.e., $\alpha^*(D'') < \alpha^*(D)$).

* Second, let us assume that $L_\beta \ne \emptyset$, and that $R_\gamma = \emptyset$ (note that the case when $L_\beta = \emptyset$, and $R_\gamma \ne \emptyset$ is symmetric). Let us denote by $C'_\delta$ the first component in $D$ that is in $L_\beta$. Then, let
$$
\begin{align*}
D' &= (X_1, \dots, X_h) \odot ((X_{h+1}, \dots, X_{a_{C'_\delta}-1}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \odot \\
&\quad (((X_{a_{C'_\delta}}, \dots, X_{a_{C_{\alpha^*}}}-1) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \cup \{l_{C'_\beta}\}) \odot \\
&\quad (((X_{a_{C_{\alpha^*}}, \dots, X_{b_{C_{\alpha^*}}}}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \cup \{l_{C'_\beta}\}) \odot
\end{align*}
$$

$$((X_{h+1}, \dots, X_{a_{C_{\alpha^*}}-1}) \cap \bigcup_{\beta \le m \le \gamma} \bar{C}'_m) \cup \{l_{C'_\beta}\} \cup (X_{b_{C_{\alpha^*}}} \cap F) \odot (X_{b_{C_{\alpha^*}}+1}, \dots, X_p).$$

With similar arguments as in the previous case, this will contradict the minimality of $\alpha$.

* Finally, let us assume that $L_\beta \neq \emptyset$, and that $R_\gamma \neq \emptyset$. Let us denote by $C_\delta^l$ the first component in $D$ that is also in $L_\beta$. Let us denote by $C_\delta^r$ the first component in $D$ that is also in $R_\gamma$. Let us assume that $C_\delta^l$ appears before $C_\delta^r$ in $D$ (the other case is symmetric). Then, let

$$
\begin{align*}
D' &= (X_1, \dots, X_h) \odot ((X_{h+1}, \dots, X_{a_{C'_\delta}-1}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \odot \\
&\quad (((X_{a_{C'_\delta}}, \dots, X_{a_{C_\delta}}-1}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \cup \{l_{C'_\beta}\}) \odot \\
&\quad (((X_{a_{C_\delta}}, \dots, X_{a_{C_{\alpha^*}}}-1) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \cup \{l_{C'_\beta}, r_{C'_\gamma}\}) \odot \\
&\quad (((X_{a_{C_{\alpha^*}}, \dots, X_{b_{C_{\alpha^*}}}}) \setminus (\bigcup_{\beta \le m \le \gamma} \bar{C}'_m)) \cup \{l_{C'_\beta}, r_{C'_\gamma}\}) \odot
\end{align*}
$$

$$((X_{h+1}, \dots, X_{a_{C_{\alpha^*}}-1} \cap \bigcup_{\beta \le m \le \gamma} \bar{C}'_m) \cup \{l_{C'_\beta}, r_{C'_\gamma}\} \cup (X_{b_{C_{\alpha^*}}} \cap F) \odot (X_{b_{C_{\alpha^*}}+1}, \dots, X_p).$$

With similar arguments as in the previous case, this will contradict the minimality of $\alpha$.

<figure><img src="image_14.png" /></figure>
### 4.2.4 Computing optimal left-to-right *g*-contiguous decompositions in polynomial-time

Finally, we show that *LtR g-contiguous {x, y}-path-decompositions* can be computed efficiently. In the following theorem, by “optimal *LtR g-contiguous {x, y}-path-decomposition of G*”, we mean a path-decomposition of minimum length among all *LtR g-contiguous {x, y}-path-decompositions of G.

**Theorem 8** Let $G = (V, E)$ be a connected simple outerplanar $n$-node graph and $x, y \in E_{\text{out}} \cup V$ such that $G \setminus x$ and $G \setminus y$ are connected, $x \neq y$, $x \notin y$, $y \notin x$ and $x$ and $y$ lie on the same internal face F of G. Let us assume that $\text{pl}(G, x, y) \le k$.

Then, an optimal *LtR g-contiguous {x, y}-path-decomposition of G* can be computed in time $O(n + k^2)$.

**Proof.** First, the connected components $C$ (and $\bar{C} = C \cup s_C$) of $G \setminus F$ can be computed in linear time. Note that these components are pairwise edge-disjoint. By Theorem 3, in global time $O(|E|)$, an optimal greedy path-decomposition $D_C$ based on $s_C$ can be computed for each such a component $\bar{C}$.

For each cut vertex $v \in F$, let $C_v$ be the set of the connected components of $G \setminus v$ that do not contain $x$ (nor $y$) and let $C_v \in C_v$ (note that $v = s_{C_v}$) be a component that maximizes $\text{dist}(h_{C_v, v}^*, v)$. Let $G'$ be obtained from $G$ by removing, for every cut-vertex $v \in F$, all components of $C_v$ but $C_v$. That is, for every cut-vertex $v$ of $F$, there is a single component of $G' \setminus v$ not containing $x$ nor $y$.

We first compute a path-decomposition for $G'$ that we then extend to a path-decomposition of $G$.

Let $(\bar{C}_1^u, \dots, \bar{C}_q^u)$ be the components $C$ such that $s_C \in P_{up}$ ordered from “left to right” (from $x_1$ to $y_1$ as in previous section), and let $(\bar{C}_1^d, \dots, \bar{C}_q^d)$ be the components $C$ such that $s_C \in P_{down}$ ordered from $x_2$ to $y_2$ (we use the same notation as in Section 4.2.3).

Note that $F$ induces an isometric subgraph of $G$ (and of $G'$) and so, by Lemma 1 and Theorem 2, $|F| = O(k)$. Therefore, since every cut-vertex of $G'$ corresponds to a single component, it follows that $q, q' = O(k)$.

For every $0 \le i \le q$, $0 \le j \le q'$, let $G[i, j]$ be the subgraph of $G$ induced by $x = \{x_1, x_2\}$ and every component $\bar{C}_{i'}^u$, $1 \le i' \le i$ and every component $\bar{C}_{j'}^d$, $1 \le j' \le j$ and adding a new edge $e_{i, j}$ between $r_{\bar{C}_i^u}$ and $r_{\bar{C}_j^d}$ of length $\text{dist}_G(r_{\bar{C}_i^u}, r_{\bar{C}_j^d})$ (this artificial edge is used to keep the same distances as in $G$ and $G'$). Let $D[i, j]$ denote an optimal *LtR g-contiguous {x, e_{i,j}}-path-decomposition of G[i, j]$.

Let $D_1 = D[i-1, j] \odot (D_{C_i^u} \cup \{r_{C_j^d}\})$ and let $D_2 = D[i, j-1] \odot (D_{C_j^d} \cup \{r_{C_i^u}\})$. Let $D' \in \{D_1, D_2\}$ be the decomposition minimizing its length. Then, by definition of *LtR g-contiguous path-decomposition*, $D'$ is an optimal *LtR g-contiguous {x, e_{i,j}}-path-decomposition of G[i, j]*. Therefore, for every $0 \le i \le q$, $0 \le j \le q'$, $D[i, j]$ can be computed in constant time from $D[i-1, j]$ and $D[i, j-1]$. Indeed, computing the length of $D_1$ (resp., $D_2$) from the one of $D[i-1, j]$ (resp., of $D[i, j-1]$) only relies on the distance between $h_{C_j^d}^*$ and $r_{C_i^u}$ (resp., between $h_{C_i^u}^*$ and $r_{C_j^d}$) and these distances can be pre-computed in linear global time (for each component $C$, a single BFS from $s_C$ is sufficient to determine $h_C^*$ and its distance to $s_C$).
Hence, once the linear time pre-processings (computation of the greedy decompositions and of the distances) have been done, an optimal $\{x, y\}$-path-decomposition $D[q, q']$ of $G'$ can be computed in time $O(k^2)$ by dynamic programming.

To conclude, to obtain the desired decomposition for $G$ from $D[q, q']$, it is sufficient, for every cut-vertex $v \in F$ and every component $C \in C_v \setminus \{C_v\}$, to insert a greedy decomposition $D_C \cup x_v$ just after the one of $D_{C_v}$ in $D[q, q']$ where $x_v \neq v$ is the (unique) vertex of $F$ not in $\bar{C}_v$ that appears in the same bags as $\bar{C}_v$ in $D[q, q']$ (by maximality of $\text{dist}(h_{\bar{C}_v}^*, v)$ when defining $C_v$, this does not increase the length of the decomposition). ■

## 4.3 Polynomial-time +1 approximation for computing the path-length of outerplanar graphs

We are finally ready to prove our main theorem. Recall that, since $G$ is outerplanar, for every subgraph $H$ of $G$, $|E(H)| = O(|V(H)|)$.

**Theorem 9** There exists an algorithm that, for every $n$-node simple connected outerplanar graph $G = (V, E)$, decides whether $p\ell(G) > k$ or returns a path-decomposition of $G$ with length at most $k+1$, in time $O(n^3(n+k^2))$.

**Proof.** For every $x, y \in E_{\text{out}} \cup V$ (possibly $x = y$), the algorithm decides whether $p\ell(G, x, y) > k$ or computes an $\{x, y\}$-path-decomposition of $G$ length at most $k+1$. By Lemma 3, such a decomposition with minimum length will be a path-decomposition of $G$ with length at most $p\ell(G) + 1$. (We need to also consider the cases when $x$ and $y$ are vertices for the recursion below).

Let us fix $x, y \in E_{\text{out}} \cup V$ and let us assume that $p\ell(G, x, y) \le k$, we present an algorithm that computes an $\{x, y\}$-path-decomposition of $G$ length at most $k+1$ in time $O(n(n+k^2))$.

If $x = y$ or $x \in y$ or $y \in x$, the Algorithm Greedy (see Section 4.1.3) computes an optimal $\{x, y\}$-path-decomposition of $G$ in linear time by Theorem 3 and we are done. So let us assume that $x \neq y$ and $x \notin y$ and $y \notin x$.

First, in linear time, the cut-vertices and internal edges separating $x$ and $y$ are computed (this can be done, e.g., using SPQR trees [15]). Let $\{e_0 = x, e_1, \dots, e_{q-1}, e_q = y\}$ where $e_i \in E_{\text{int}} \cup V$ for every $0 < i < q$ be the set of those minimal $x$-$y$-separators in order they are met when going from $x$ to $y$. In particular, if $x$ is an edge only incident to the external face, then $e_1$ is the vertex of $x$ that is closest to $y$. For every $0 < i < q-1$, $e_i \neq e_{i+1}$ (they may intersect) and either $e_i$ and $e_{i+1}$ share a same internal face $F_i$, or $e_i$ and $e_{i+1}$ are vertices and $\{e_i, e_{i+1}\} \in E_{\text{out}}$. Let $C$ be the set of connected components of $G \setminus e_i$ for some $0 \le i \le q$ that contain neither $x$ nor $y$. That is, for every $C \in C$, either $N(C) = x$ or $N(C) = y$, or there exists $0 \le i \le q$ and $v \in e_i$ (or $v = e_i$ if $e_i$ is a vertex) such that $N(C) = \{v\}$. Note that this decomposition into several connected components is done once for all at the beginning of the execution of the algorithm. In particular, it is not done anymore in the recursive calls described below and therefore it counts only for a linear time in the total time complexity.

Let $F_0$ be an internal face that is common to both $x$ and $e_1$ (i.e., $x$ and $e_1$ belong to the cycle composing the face) if such face exists. Note that, if such a face $F_0$ does not exist, then either $x, e_1 \in V$ are adjacent vertices such that $\{x, e_1\} \in E_{\text{out}}$ only belongs to
the external face, or $e_1 \in x$ and $x$ only belongs to the external face. In the latter case, we set $F_0$ to be $x \cup \{e_1\}$, i.e., $F_0$ equals to $x$ (if $x$ is an edge, in which case it contains $e_1$) or to the edge $\{x, e_1\}$ (which is only incident to the external face).

Let $C'$ be the set of connected components of $G \setminus F_0$ that do not contain $y$ and let $C_y$ be the component of $G \setminus F_0$ that contains $y$ (if $y = e_1$, $C_y$ does not need to be defined). Let $C'' = C' \setminus C$. Let $G_x$ (resp., $G'_x$) be the subgraph induced by $F_0$ and $C'$ (resp., $C''$). Let $G_y$ be the subgraph induced by $C_y$ and $V(e_1)$ (if $y = e_1$, $G_y$ does not need to be defined).

If $e_1 \neq y$, our algorithm first recursively computes a $\{e_1, y\}$-path-decomposition $D_y$ of $G_y$ with length at most $k+1$ in time $O(|V(G_y)|(|V(G_y)| + k^2))$ (by induction on the size of the graph). Then (should $y$ be equal to $e_1$ or not), note that $G'_x \setminus x$ and $G''_x \setminus e_1$ are connected and $e_1 \neq x$.

* If $e_1 \in x$ (or $\{x, e_1\} \in E_{out}$ and this edge only belongs to the external face), let $D'_x$ be an optimal greedy $\{x, e_1\}$-path-decomposition of $G'_x$ computed in time $O(|E(G'_x)|)$ by Theorem 3.

* Otherwise, $x$ and $e_1$ share a same face $F_0$ and so the conditions of Theorem 8 are fulfilled and an $\{x, e_1\}$-path-decomposition $D'_x$ of $G'_x$ with length at most $k+1$ can be computed in time $O(|V(G'_x)| + k^2)$.

Then, for every $C \in C' \cap C$, let $v_C \in V$ be such that $N(C) = \{v_C\}$. Our algorithm computes an optimal greedy path-decomposition $D_c$ of $\bar{C}$ based on $v_C$, for every $C \in C' \cap C$. By Theorem 3, this can be done in total time $O(\sum_{C \in C' \cap C} |E(C)|) = O(|E(G_x)|)$. Using several times (one time per component of $C' \cap C$) some of the Lemmas 5-9 (depending on whether $x$ and $e_1$ are edges or not, whether they intersect or not, and whether $N(C)$ intersects only $x$ or $e_1$ or both), an $\{x, e_1\}$-path-decomposition $D_x$ of $G_x$ with length at most $k+1$ can be computed from $D'_x$ and the decompositions $D_C$, for all $C \in C' \cap C$. Finally, from Lemma 10, the desired $\{x, y\}$-path-decomposition of $G$ with length at most $k+1$ is obtained from $D_x$ and $D_y$. So, the total time-complexity of our algorithm is $O(|V(G_y)|(|V(G_y)| + k^2)) + O(|V(G_x)| + k^2) = O(n(n + k^2))$. ■

# 5 Further work

The next step would be to design a polynomial time exact algorithm (if it exists) to compute the pathlength of outerplanar graphs. Note that the increase of the length (+1) in our approximation algorithm comes from the contiguous property. The example of Figure 5 shows that we cannot avoid this increase if we keep the contiguous property. Moreover, the *LtR* property has been proven from a contiguous path-decomposition. Therefore, this proof needs also to be adapted for the exact case. Another question would be to know whether our algorithm for trees can be adapted to chordal graphs. Moreover, the complexity of computing the pathlength (or treelength) of planar graphs is still open. Finally, another possible research direction would be to study the computation of pathlength (or treelength) parameterized by the treewidth of the input graph, e.g., by using Courcelle's theorem.
References

[1] R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. *SIAM J. Discret. Math.*, 31(2):1217–1243, 2017.

[2] Eli Berger and Paul D. Seymour. Bounded-diameter tree-decompositions. *Comb.*, 44(3):659–674, 2024. URL: https://doi.org/10.1007/s00493-024-00088-1, doi:10.1007/S00493-024-00088-1.

[3] Achim Blumensath and Bruno Courcelle. Monadic second-order definable graph orderings. *Log. Methods Comput. Sci.*, 10(1), 2014.

[4] H. L. Bodlaender and F. V. Fomin. Approximation of pathwidth of outerplanar graphs. *J. Alg.*, 43(2):190–200, 2002.

[5] Hans L. Bodlaender. A partial $k$-arboretum of graphs with bounded treewidth. *Theor. Comput. Sci.*, 209(1-2):1–45, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00228-4, doi:10.1016/S0304-3975(97)00228-4.

[6] D. Coudert, G. Ducoffe, and N. Nisse. To Approximate Treewidth, Use Treelength! *SIAM J. on Disc. Maths.*, 30(3):13, 2016.

[7] D. Coudert, F. Huc, and J.-S. Sereni. Pathwidth of outerplanar graphs. *J. Graph Theory*, 55(1):27–41, 2007.

[8] Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, and Simon Nivelle. Treelength of series-parallel graphs. *Discret. Appl. Math.*, 341:16–30, 2023. URL: https://doi.org/10.1016/j.dam.2023.07.022, doi:10.1016/J.DAM.2023.07.022.

[9] Thomas Dissaux and Nicolas Nisse. Pathlength of outerplanar graphs. In *15th Latin American Symposium on Theoretical Informatics (LATIN'22)*, volume 13568 of LNCS, pages 172–187. Springer, 2022.

[10] Y. Dourisboure and C. Gavoille. Tree-decompositions with bags of small diameter. *Discret. Math.*, 307(16):2008–2029, 2007.

[11] F. F. Dragan, E. Köhler, and A. Leitert. Line-distortion, bandwidth and path-length of a graph. *Algorithmica*, 77(3):686–713, 2017.

[12] Feodor F. Dragan and Arne Leitert. Minimum eccentricity shortest paths in some structured graph classes. *J. Graph Algorithms Appl.*, 20(2):299–322, 2016.

[13] G. Ducoffe, S. Legay, and N. Nisse. On the complexity of computing treebreadth. *Algorithmica*, 82(6):1574–1600, 2020.

[14] Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, and Roger Wattenhofer. Dynamic analysis of the arrow distributed protocol. *Theory Comput. Syst.*, 39(6):875–901, 2006.

[15] John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. *SIAM J. Comput.*, 2(3):135–158, 1973.
[16] Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In *42nd Annual Symposium on Foundations of Computer Science, FOCS*, pages 10–33. IEEE, 2001.

[17] Adrian Kosowski, Bi Li, Nicolas Nisse, and Karol Suchan. *k*-chordal graphs: From cops and robber to compact routing via treewidth. *Algorithmica*, 72(3):758–777, 2015.

[18] R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In *47th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2006)*, pages 119–132, 2006.

[19] Daniel Lokshtanov. On the complexity of computing treelength. *Discret. Appl. Math.*, 158(7):820–827, 2010.

[20] Sandra L. Mitchell. Linear algorithms to recognize outerplanar and maximal outer-planar graphs. *Information Processing Letters*, 9(5):229–232, 1979.

[21] B. Mohar and C. Thomassen. *Graphs on Surfaces*. Johns Hopkins Studies in Nineteenth C Architecture Series. Johns Hopkins University Press, 2001. URL: https://books.google.fr/books?id=_VFKscYKSicC.

[22] Burkhard Monien and Ivan Hal Sudborough. Min cut is NP-complete for edge weighted trees. *Theor. Comput. Sci.*, 58:209–229, 1988.

[23] J. B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. *Science*, 290(5500):2319–2323, 2000.