Treewidth of Outer $𝒌$-Planar Graphs

The authors of [7] proved that every outer $k$-planar graph has treewidth at most $1.5k+2$. They also presented a lower bound of $k+2$ for every even $k$. We present an infinite family of outer $k$-planar graphs with treewidth at least $1.5k+0.5$, showing that the multiplicative constant $1.5$ in the upper bound cannot be improved; see Section 3.

We also improve the upper bounds for the treewidth and separation number of outer min-$k$-planar graphs. It was previously known that the treewidth of such graphs is at most $3k+1$ and the separation number is at most $2k+1$ [7]. We give an upper bound of $3\cdot \lfloor k/2\rfloor +4$ for the treewidth (see Section 4) and an upper bound of $2\cdot \lfloor k/2\rfloor +4$ for the separation number (see Section 5). Both multiplicative constants are optimal, as the lower bounds for outer $k$-planar graphs also hold for outer min-$k$-planar graphs – namely, our lower bound of $1.5k+0.5$ for the treewidth and the lower bound of $k+2$ for the separation number presented in [7].

Consider an outer min-$k$-planar drawing $\mathrm{\Gamma }$ of $G$. Let $u$ and $v$ be consecutive vertices in the cyclic order defined by $\mathrm{\Gamma }$. Suppose, for contradiction, that $uv\notin E(G)$. Note that the graph $G+uv$ has an outer min-$k$-planar drawing defined by the same cyclic order as $\mathrm{\Gamma }$, contradicting the maximality of $G$. $◀$

A graph $G$ is expanded outer min-$k$-planar if $G$ is an outer min-$k$-planar graph with $\mathrm{\Delta }(G)\le 3$ and its outer face is bounded by a cycle in some outer min-$k$-planar drawing of $G$.

Let us assume that $G$ is maximal outer min-$k$-planar. Now, in order to obtain $G^{\prime }$ from $G$, we perform the following transformation to every vertex $v$ of $G$ with $\mathrm{deg}(v)\ge 4$. The transformation is depicted in Figure 1. Let $w_0,w_1,\mathrm{\dots },w_s,w_{s+1}$ be all neighbors of $v$ in clockwise order, with edges $v{w}_0$ and $v{w}_{s+1}$ incident to the outer face of $G$. We replace $v$ with a path $v_1,\mathrm{\dots },v_s$, put it on the outer face of $G$ in counterclockwise order, in the place of $v$. We connect this path to vertices $w_0$ and $w_{s+1}$ by adding edges $v_1{w}_0$ and $v_s{w}_{s+1}$. Finally, for every $1\le i\le s$, we add an edge $v_i{w}_i$ that corresponds to an edge $v{w}_i$ in the original graph. It is easy to see that $G$ is a minor of $G^{\prime }$ and the ordering of corresponding edges in $G^{\prime }$ matches the one in $G$. Moreover, the crossings in the resulting graph naturally correspond to the crossings in the original graph. $◀$

The vertices $v_1,\mathrm{\dots },v_s$ obtained in the proof as a replacement of $v$ are called images of $v$. The vertex $v$ is the origin of these vertices, which we denote as $\mathrm{org}(v_i)=v$. If the transformation was not performed for some vertex $v$ of $G$, i.e. $\mathrm{deg}(v)\le 3$, then $v$ is an image and origin of itself.

Since removing edges increases neither the treewidth nor the separation number, we are interested in the properties of maximal outer min-$k$-planar graphs. Also, taking a minor does not increase treewidth, so we work with expanded graphs when establishing upper bounds on treewidth.

Notice that the drawing of $G_k$ in Figure 2 is $k$-outerplanar. By the fact that $k$-outerplanar graphs have treewidth at most $3k-1$ [3, Theorem 83], we get $\mathrm{tw}(G_k)\le 3k-1$.

To prove that $\mathrm{tw}(G_k)\ge 3k-1$, we construct a bramble of order $3k$. Then, using Theorem 1, we get $\mathrm{tw}(G_k)\ge 3k-1$. Let ${ℬ}_1$ be a family consisting of every subset of $V(G_k)$ that is a union of an extended row of $G_k$ and a column of $Q_k$. Let ${ℬ}_2$ be a family consisting of every subset of $V(G_k)$ that is a union of a row of $R_k$ and a column of $R_k$. The set $ℬ={ℬ}_1\cup {ℬ}_2$ forms a bramble of $G_k$, since each subgraph induced by an element of $ℬ$ is connected and every two such subgraphs have at least one common vertex.

Consider any hitting set $S$ of $ℬ$. Let $q$ and $r$ be the number of vertices of $S$ in $V(Q_k)$ and in $V(R_k)$, respectively. We would like to show that $|S|=q+r\ge 3k$. Note that $r\ge k$, as otherwise there is a row and a column of $R_k$ not containing any element of $S$, and thus there is an element of ${ℬ}_2$ not hit by $S$.

If $q\ge 2k$, then $q+r\ge 3k$. Otherwise, let $q=2k-l$ for some positive integer $l$. Now, we can find at least $l$ columns and at least $l$ rows of $Q_k$ not intersecting $S$. These $l$ rows are contained in $l(k+1)$ extended rows. Each of them has to intersect $S$ at some vertex of $R_k$, because otherwise we can find a column of $Q_k$ and an extended row not intersecting $S$ that form an element of ${ℬ}_1$. The extended rows restricted to $R_k$ are pairwise disjoint, so we have $r\ge l(k+1)$. Summing up, we get $q+r\ge 2k-l+l(k+1)=2k+lk\ge 2k+k=3k$, which concludes the proof. $◀$

Let $F_k$ be the following modification of $G_k$ depicted in Figure 3. We set $\mathrm{\ell }(i)=(k-i)(k+1)$ for $1\le i\le k$, and $\mathrm{\ell }(i)=(i-k-1)(k+1)$ for $k+1\le i\le 2k$. We remove every edge between the grids $Q_k$ and $R_k$. For every $1\le i\le 2k$, we add a path $Z_i$ of length $\mathrm{\ell }(i)$ on new vertices $z_{i,0},z_{i,1},\mathrm{\dots },z_{i,\mathrm{\ell }(i)}$. Note that

We also add a path $W_i$ of length $k$ on new vertices $w_{i,1},w_{i,2},\mathrm{\dots },w_{i,k+1}$. We connect $v_{i,2k}$ with $Z_i$ by adding the edge $v_{i,2k}{z}_{i,0}$. Next, we connect $Z_i$ with $W_i$ by adding the edge $z_{i,\mathrm{\ell }(i)}{w}_{i,k+1}$ for $1\le i\le k$, or the edge $z_{i,\mathrm{\ell }(i)}{w}_{i,1}$ for $k+1\le i\le 2k$. Finally, we connect $W_i$ with $R_k$ by adding the edges $w_{i,j}{u}_{(i-1)(k+1)+j,1}$ for every $1\le j\le k+1$.

To see that $G_k$ is a minor of $F_k$, it is enough to contract, for every $1\le i\le 2k$, vertex $v_{i,2k}$ with all vertices of the paths $Z_i$ and $W_i$. Since taking a minor does not increase the treewidth, we obtain the following corollary.

We describe an outer $(2k-1)$-planar drawing of $F_k$, as depicted in Figure 4. We call the set of vertices $\{v_{i,j}:1\le i\le k,1\le j\le 2k\}$ the upper part of $Q_k$. The other vertices of $Q_k$ are called the lower part of $Q_k$. We define a cyclic order of the vertices of $F_k$ by arranging them in clockwise order from some selected starting point on a circle.

First, we place the vertices of the upper part of $Q_k$ in column-by-column order (see Figure 4(b)):

We divide the vertices of paths $Z_i$ and $W_i$, for $1\le i\le k$, into $k$ groups, as follows. The $i$-th group contains the vertices of $W_i$ and the vertex $z_{i,\mathrm{\ell }(i)}$. If $i\ge 2$, the $i$-th group also contains vertices $z_{a,b}$ for and . In the drawing, we place the groups of indices $k,k-1,\mathrm{\dots },1$, in this order. We arrange the vertices in the $i$-th group, for $2\le i\le k$, in the order (see Figure 4(c)):

The group of index 1 has vertices arranged in the order: $z_{1,\mathrm{\ell }(1)},w_{1,k+1},w_{1,k},\mathrm{\dots },w_{1,1}$.

Next, we put the vertices of $R_k$ in row-by-row order (see Figure 4(d)):

The vertices of $F_k$ that are not placed yet are in the lower part of $Q_k$ or in the paths $Z_i$, $W_i$ with $k+1\le i\le 2k$. We arrange them in counterclockwise order from the starting point and place them between the starting point and the vertices of $R_k$. The order is symmetric, with respect to the starting point, to the one used to arrange the upper part of $Q_k$ and the paths $Z_i$, $W_i$ with $1\le i\le k$. Every vertex $v_{i,j}$, where $k+1\le i\le 2k$ and $1\le j\le 2k$, is placed symmetrically to $v_{2k-i+1,j}$. Vertex $z_{i,j}$, where $k+1\le i\le 2k$ and $0\le j\le \mathrm{\ell }(i)$, is placed symmetrically to $z_{2k-i+1,j}$, and vertex $w_{i,j}$, where $k+1\le i\le 2k$ and $1\le j\le k+1$, is placed symmetrically to $w_{2k-i+1,k-j+2}$. The symmetrical drawing of the $i$-th group, for every $1\le i\le k$, forms the group of index $2k-i+1$.

Now, we partition the edges into several numbered types. For the edges of each type, we show that they cross at most $2k-1$ other edges.

Edges of $Q_k$:

1. 1.

   The “column” edges of the upper or lower part of $Q_k$, that is, the edges $v_{i,j}{v}_{i+1,j}$, for $1\le i\le 2k-1,i\ne k$ and $1\le j\le 2k$. They cross no other edges.

2. 2.

   The “column” edges between the upper part and the lower part of $Q_k$, that is, the edges $v_{k,j}{v}_{k+1,j}$, for $1\le j\le 2k$. Each of these edges crosses $k-1$ edges of type 3 of the upper part of $Q_k$, and $k-1$ edges of type 3 of the lower part of $Q_k$. The edge $v_{k,1}{v}_{k+1,1}$ does not cross any edges.

3. 3.

   The “row” edges of $Q_k$, that is, the edges $v_{i,j}{v}_{i,j+1}$, for $1\le i\le 2k$ and $1\le j\le 2k-1$. Each of these edges crosses at most $2(k-1)$ edges of type 3 (and type 4, for $j=2k-1$), and additionally at most one edge of type 2.

Edges between $Q_k$ and the groups:

1. 4.

   Each edge $v_{i,2k}{z}_{i,0}$, for $1\le i\le k$, crosses $2(k-1)$ edges in total: $2(i-1)$ edges of types 3, 4 incident to vertices $v_{j,2k}$, for all $j\in \{1,\mathrm{\dots },i-1\}$; and $2(k-i)$ edges incident to vertices $z_{j,0}$, for all $j\in \{i+1,\mathrm{\dots },k\}$. By symmetry, each edge $v_{i,2k}{z}_{i,0}$, for $k+1\le i\le 2k$, also crosses exactly $2(k-1)$ edges.

Edges of the groups:

1. 5.

   Each edge $z_{i,\mathrm{\ell }(i)}{w}_{i,k+1}$, for $1\le i\le k$, crosses exactly $2(i-1)$ edges incident to the vertices $z_{i-1,\mathrm{\ell }(i)},\mathrm{\dots },z_{1,\mathrm{\ell }(i)}$. By symmetry, each edge $z_{i,\mathrm{\ell }(i)}{w}_{i,1}$, for $k+1\le i\le 2k$, also crosses exactly $2(2k-i)$ edges.

2. 6.

   Each edge of the path $Z_i$, for $1\le i\le 2k$, crosses at most $2(k-2)$ edges incident to at most $k-2$ vertices of some paths $Z_j$ with $j\in \{1,\mathrm{\dots },2k\}$, and at most three edges incident to some vertex $w_{a,b}\in V(W_j)$ with $j\in \{1,\mathrm{\dots },2k\}$.

3. 7.

   Each edge of the path $W_i$, for $1\le i\le k$, crosses $2(i-1)$ edges incident to $i-1$ vertices of some paths $Z_j$ with $j\in \{1,\mathrm{\dots },k\}$. By symmetry, each edge of the path $W_i$, for $k+1\le i\le 2k$, also crosses $2(2k-i)$ edges.

Edges between the groups and $R_k$:

1. 8.

   Each edge $w_{i,j}{u}_{(i-1)(k+1)+j,1}$, for $1\le i\le 2k$ and $1\le j\le k+1$, crosses at most $k-1$ edges of some paths $Z_a$ with $a\in \{1,\mathrm{\dots },2k\}$, and at most $k-1$ edges of $R_k$ of type 10.

Edges of $R_k$:

1. 9.

   The “row” edges of $R_k$, that is, the edges $u_{i,j}{u}_{i,j+1}$, for $1\le i\le 2k(k+1)$ and $1\le j\le k-1$. They cross no other edges.

2. 10.

   The “column” edges of $R_k$, that is, the edges $u_{i,j}{u}_{i+1,j}$, for $1\le i\le 2k(k+1)-1$ and $1\le j\le k$. Each of these edges crosses at most $2(k-1)$ other edges of this type and at most one edge of type 8.

$◀$

By Theorem 6, the graph $F_{\frac{k+1}{2}}$ is outer $k$-planar, and by Corollary 5, it has treewidth at least $3\cdot \frac{k+1}{2}-1=1.5k+0.5$. $◀$

Let $f$ be an inner face of $G_P$. If $f$ is adjacent to $f_o$, then $\mathrm{dist}(f^{\ast },f_o^{\ast })=1$. Otherwise, let $v$ be a vertex of $G_P$ incident to $f$. Since $G$ is expanded, the vertex $v$ is inner, and hence it lies on an edge $e$ of $G$ that crosses at most $k$ other edges. Let $v_0,v_1,\mathrm{\dots },v_s,v_{s+1},\mathrm{\dots },v_{s+t+1}$ be all vertices lying on $e$, listed in the order along $e$, where $v_s=v$ and $v_{s+1}$ is a neighbor of $v$ that is incident to $f$. We may assume that $s\le t$, i.e. $v_s$ is closer to an endpoint of the edge $e$ than $v_{s+1}$ to the other endpoint of $e$. Note that at most $k+2$ vertices lie on $e$ (two endpoints and at most $k$ crossing points), so $s+t+2\le k+2$. Together with the previous inequality, this implies $s\le k/2$. The number $s$ is an integer so $s\le \lfloor k/2\rfloor$.

We inductively define a sequence $w_s,w_{s-1},\mathrm{\dots },w_0$ of vertices. Vertex $w_s$ is the neighbor of $v_s$ that is incident to $f$ and does not lie on $e$. For every $i=s-1,\mathrm{\dots },0$, the vertex $w_i$ is one of the two neighbors of $v_i$ not lying on $e$, chosen so that $w_i$, $v_i$, $v_{i-1}$ and $w_{i-1}$ are incident to the same face of $G_P$. Let $e_i$ denote the edge $v_i{w}_i$. Note that the path formed by the edges $e_s^{\ast },\mathrm{\dots },e_0^{\ast }$ connects $f^{\ast }$ with $f_o^{\ast }$ (since $e_0$ is incident to $f_o$). Hence, $\mathrm{dist}(f^{\ast },f_o^{\ast })\le s+1\le \lfloor k/2\rfloor +1$. $◀$

Let $v$ be an inner vertex of $G_P$. Since we forbid common crossing points of three edges of $G$, the vertex $v$ has four neighbors, which we denote by $w_1,w_2,w_3,w_4$ in clockwise order. The splitting of the vertex $v$ replaces it with two vertices $v_1$ and $v_2$ connected by an edge, and adds edges $v_1{w}_1$, $v_1{w}_2$ and $v_2{w}_3$, $v_2{w}_4$. We fix a planar embedding of the new graph by placing $v_1$, $v_2$ very close to where $v$ was drawn. We say that vertices $v_1$ and $v_2$ lie on the same edges as the vertex $v$. Moreover, we call the edge $v_1{v}_2$ an auxiliary edge. After splitting $v$, every edge of $G_P$ has an edge corresponding to it, and every face of $G_P$ corresponds to a new one in a natural way. Additionally, the dual graph has one new edge, which is dual to $v_1{v}_2$.

Let $G_S$ denote the split planarization of the outer min-$k$-planar graph $G$, that is, the graph $G_P$ with all inner vertices split. See Figure 5 for an example. Observe that there is a one-to-one correspondence between $V(G_P^{\ast })$ and $V(G_S^{\ast })$. Further, every edge of $G_P^{\ast }$ has a corresponding edge of $G_S^{\ast }$. The following lemma shows how the properties of a spanning tree $T_P$ of $G_P$ and a spanning tree $\mathrm{dual}(T_P)$ of the dual graph $G_P^{\ast }$ are preserved after splitting the vertices of $G_P$.

Let $G_P$ be a planarization of $G$. By Lemmas 9 and 10, there exists a spanning tree $T_P^{\ast }$ of $G_P^{\ast }$ that is rooted at $f_o^{\ast }$ whose vertices have depth at most $\lfloor k/2\rfloor +1$. Let $T_P=\mathrm{dual}(T_P^{\ast })$ denote the spanning tree of $G_P$.

Let $G_S$ denote the graph obtained from $G_P$ by splitting each of its inner vertices. After this transformation, let $T_S^{\ast }$ be a tree constructed of edges corresponding to those of $T_P^{\ast }$. Clearly, $T_S^{\ast }$ is a spanning tree of the graph $G_S^{\ast }$. The spanning tree $T_S=\mathrm{dual}(T_S^{\ast })$ of $G_S$ contains all auxiliary edges of $G_S$, because none of the duals of auxiliary edges are in $E(T_S^{\ast })$, as they were not in $E(T_P^{\ast })$. $◀$

Now, we are ready to prove the main result of this section.

By Observation 3 we may assume that $G$ is an expanded outer min-$k$-planar graph. Let $G_S$ be the split planarization of $G$. By Lemma 11 there exists a spanning tree $T_S$ of $G_S$ and a spanning tree $T_S^{\ast }=\mathrm{dual}(T_S)$ of $G_S^{\ast }$ rooted at $f_o^{\ast }$ such that $0pt(f^{\ast })\le \lfloor k/2\rfloor +1$ for every vertex $f^{\ast }\in V(G_S^{\ast })$ and $E(T_S)$ contains all auxiliary edges of $G_S$.

We orient the edges of $G$ as follows. Edges incident to the outer face are oriented clockwise, while all other edges are oriented arbitrarily. Observe that every vertex of $G$ has at most two incoming edges.

Now, we construct the tree decomposition $𝒯=(T_S,B)$ of the graph $G$. The bags of $𝒯$ are indexed by the vertices of the spanning tree $T_S$. We place vertices of $G$ into bags using the following rules.

1. 1.

   For every outer vertex $v\in V(G_S)$, we place $v$ into the bag $B_v$.

2. 2.

   For every oriented edge $(x,y)$ of $G$, we place $x$ into the bag $B_y$.

3. 3.

   For every oriented edge $(x,y)$ of $G$, and for every inner vertex $v\in V(G_S)$ lying on $(x,y)$, we place $x$ into the bag $B_v$.

4. 4.

   For every inner face $f$ and every edge $e^{\ast }$ on the path from $f^{\ast }$ to $f_o^{\ast }$ in $T_S^{\ast }$, where $e$ lies on the edge $(x,y)$ of $G$, we place $x$ into the bag $B_v$ for each vertex $v$ incident to $f$.

Note that, in rule 4, the edge $e$ is not in $E(T_S)$, so it is not an auxiliary edge, which implies that it is lying only on a single edge of $G$.

For every edge $(x,y)$ of $G$, by rules 1 and 2, the bag $B_y$ contains both $x$ and $y$. Moreover, every vertex of $G$ is present in some bag. So, to prove that $𝒯$ is a tree decomposition of $G$, it suffices to show that for every vertex $x\in V(G)$, the set $\{w:x\in B_w\}$ induces a connected subtree in $T_S$.

Fix a vertex $x$ and an edge $(x,y)$ of $G$. Let $e=uv$ be an edge lying on $(x,y)$ such that $e\notin E(T_S)$. Assume that $e^{\ast }=f_1^{\ast }{f}_2^{\ast }$ and $0p{t}_{T_S^{\ast }}(f_2^{\ast })=0p{t}_{T_S^{\ast }}(f_1^{\ast })+1$. Let $T_e^{\ast }$ be a subtree of $T_S^{\ast }$ induced by the set of all descendants of $f_2^{\ast }$, including $f_2^{\ast }$. Define $F_e=\{f:f^{\ast }\in V(T_e^{\ast })\}$ and let $\mathrm{boundary}(F_e)$ be the set of vertices incident to some face in $F_e$. Observe that, by rule 4, $x$ is placed into all bags indexed by $\mathrm{boundary}(F_e)$. The set $\mathrm{boundary}(F_e)$ induces a connected subgraph of $T_S$, i.e. $T_S[\mathrm{boundary}(F_e)]$ is connected, containing both $u$ and $v$. Note that the bags of $𝒯$, into which we placed $x$ by rule 4, are exactly the bags of vertices of $T_S$ that are in $\mathrm{boundary}(F_e)$ for some edge $e\notin E(T_S)$ lying on some edge $(x,y)$ of $G$.

By rules 1, 2 and 3, $x$ is contained in all bags $B_w$ such that $w$ lies on $(x,y)$ for some edge $(x,y)$ of $G$. We claim that the vertices indexing these bags, together with the vertices indexing bags we placed $x$ into by rule 4, form a connected subgraph of $T_S$. To see that, we show that for every vertex $w$ with $x\in B_w$, $w$ is connected to $x$ by a walk in $T_S$ such that bags indexed by the vertices of this walk contain $x$.

If $w$ lies on an edge $(x,y)$ of $G$ then, in order to construct this walk, we start at vertex $w$. We iterate over consecutive edges lying on $(x,y)$ between $w$ and $x$, starting at the edge incident to $w$. If the current edge $e$ is in $E(T_S)$, then we extend the walk by $e$. Otherwise, $e\notin E(T_S)$. As $T_S[\mathrm{boundary}(F_e)]$ is connected and every bag of a vertex in $\mathrm{boundary}(F_e)$ contains $x$, we can extend the walk by some path in $T_S[\mathrm{boundary}(F_e)]$ connecting the endpoints of $e$. See Figure 5(b) for an example of such a walk.

If $w$ is in the set $\mathrm{boundary}(F_e)$ for some edge $e$ lying on $(x,y)$, then we begin the walk with a path contained in $\mathrm{boundary}(F_e)$ between $w$ and an endpoint $v$ of $e$. We extend this walk by a walk between $v$ and $x$, whose existence we have already proven.

Next, we bound the size of the bags in $𝒯$. Consider an inner vertex $v$ of $T_S$. It lies on exactly two edges of $G$, so by rule 3 we placed two vertices into $B_v$. Also, $v$ is incident to three non-outer faces of $G_S$. For every such face $f$ and every edge $e^{\ast }$ on the path from $f^{\ast }$ to $f_o^{\ast }$ in $T_S^{\ast }$, by rule 4 we placed one vertex into $B_v$. By Lemma 11 we have $0pt(f^{\ast })\le \lfloor k/2\rfloor +1$, so each such path has at most $\lfloor k/2\rfloor +1$ edges. Thus, $\left|B_v\right|\le 2+3\cdot \left(\lfloor k/2\rfloor +1\right)$. Now, consider an outer vertex $v$ of $T_S$. By rules 1 and 2, the bag $B_v$ contains $v$ and at most two other endpoints of edges incoming to $v$ in $G$. Also, $v$ is incident to two non-outer faces of $G_S$. Hence, we derive a bound $\left|B_v\right|\le 3+2\cdot \left(\lfloor k/2\rfloor +1\right)$. The width of the constructed tree decomposition is at most

$◀$

For every edge $xy\in E(T)$, after removing it from $T$, we obtain two connected components $C_x$ and $C_y$ of $T$ such that $x\in V(C_x)$ and $y\in V(C_y)$. We define $S_{x,y}={\bigcup }_{v\in V(C_x)}{B}_v$ and $S_{y,x}={\bigcup }_{v\in V(C_y)}{B}_v$. It is a well known fact that the pair $(S_{x,y},S_{y,x})$ is a separation of $G$ of order $\left|S_{x,y}\cap S_{y,x}\right|=\left|B_x\cap B_y\right|\le a$.

We claim that there exists an edge $xy\in E(T)$ such that $(S_{x,y},S_{y,x})$ is a balanced separation of $G$. Suppose the contrary. Then for every $xy\in E(T)$ it holds that $\left|S_{x,y}\setminus S_{y,x}\right|>\frac{2}{3}n$ or $\left|S_{y,x}\setminus S_{x,y}\right|>\frac{2}{3}n$, where $n=\left|V(G)\right|$. Now, we orient every edge of $T$. If the first inequality holds then we orient $xy$ as $(y,x)$, in the other case as $(x,y)$. Also, note that $\left|S_{x,y}\setminus S_{y,x}\right|>\frac{2}{3}n$ implies .

The tree $T$ with oriented edges is an acyclic graph, so there exists a sink, that is, a vertex in $T$ such that all edges incident to $x$ are oriented towards $x$. Let $\{y_1,\mathrm{\dots },y_d\}$, where $d\le 3$, be the set of neighbors of $x$ in $T$. We have . Moreover,

since every vertex of $G$ is in at least two bags of $𝒯$. We obtain the following inequalities

which is a contradiction. $◀$

Now, we are ready to establish an upper bound on the separation number of outer min-$k$-planar graphs.

The class of outer min-$k$-planar graphs is closed under taking subgraphs. Therefore, it suffices to find a balanced separation of order at most $2\cdot \lfloor k/2\rfloor +4$ for every maximal outer min-$k$-planar graph $G$. Let $H$ be an expanded outer min-$k$-planar graph obtained from $G$ by Observation 3. By Theorem 12, there exists a tree decomposition $𝒯=(T_S,B)$ of $H$, where $T_S$ is a spanning tree of the split planarization of $H$. From the proof of Theorem 12, it follows that $\mathrm{\Delta }(T_S)\le 3$ and that every vertex $v\in V(H)$ is in at least two bags of $𝒯$ (since there is an oriented edge $(v,w)$ in $H$, so $v\in B_v$ and $v\in B_w$).