An improved planar graph product structure theorem

Torsten Ueckerdt ²²2Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany ([email protected]). David R. Wood ⁵⁵5School of Mathematics, Monash University, Melbourne, Australia ([email protected]). Research supported by the Australian Research Council. Wendy Yi ²²footnotemark: 2

Abstract

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph $G$ there is a graph $H$ with treewidth at most 8 and a path $P$ such that $G\subseteq H\boxtimes P$ . We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.

1 Introduction

This paper is motivated by the following question: what is the global structure of planar graphs? Recently, Dujmović et al. [12] gave an answer to this question that describes planar graphs in terms of products of simpler graphs, in particular, graphs of bounded treewidth. In this note, we improve this result in two respects. To describe the result from [12] and our improvement, we need the following definitions.

A tree-decomposition of a graph $G$ is a collection $(B_{\_}x\subseteq V(G):x\in V(T))$ of subsets of $V(G)$ (called bags) indexed by the nodes of a tree $T$ , such that:

(a)

for every edge $uv\in E(G)$ , some bag $B_{\_}x$ contains both $u$ and $v$ , and
(b)

for every vertex $v\in V(G)$ , the set $\{x\in V(T):v\in B_{\_}x\}$ induces a non-empty (connected) subtree of $T$ .

The width of a tree decomposition is the size of the largest bag minus 1. The treewidth of a graph $G$ , denoted by $\operatorname{tw}(G)$ , is the minimum width of a tree decomposition of $G$ . These definitions are due to Robertson and Seymour [21]. Treewidth is recognised as the most important measure of how similar a given graph is to a tree. Indeed, a connected graph with at least two vertices has treewidth 1 if and only if it is a tree. See [15, 20, 3] for surveys on treewidth.

A tree-decomposition $(B_{\_}x:x\in V(T))$ of a graph $G$ is $k$ -simple, for some $k\in\mathbb{N}$ , if it has width at most $k$ , and for every set $S$ of $k$ vertices in $G$ , we have $|\{x\in V(T):S\subseteq B_{\_}x\}|\leqslant 2$ . The simple treewidth of a graph $G$ , denoted by $\operatorname{stw}(G)$ , is the minimum $k\in\mathbb{N}$ such that $G$ has a $k$ -simple tree-decomposition. Simple treewidth appears in several places in the literature under various guises [16, 17, 18, 22]. The following facts are well-known: A graph has simple treewidth 1 if and only if it is a linear forest. A graph has simple treewidth at most 2 if and only if it is outerplanar. A graph has simple treewidth at most 3 if and only if it has treewidth at most 3 and is planar [17]. The edge-maximal graphs with simple treewidth 3 are ubiquitous objects, called planar 3-trees or stacked triangulations in structural graph theory and graph drawing [2, 17], called stacked polytopes in polytope theory [7], and called Apollonian networks in enumerative and random graph theory [14]. It is also known and easily proved that $\operatorname{tw}(G)\leqslant\operatorname{stw}(G)\leqslant\operatorname{tw}(G)+1$ for every graph $G$ (see [16, 22]).

The strong product of graphs $A$ and $B$ , denoted by $A\boxtimes B$ , is the graph with vertex set $V(A)\times V(B)$ , where distinct vertices $(v,x),(w,y)\in V(A\boxtimes B)$ are adjacent if (1) $v=w$ and $xy\in E(B)$ , or (2) $x=y$ and $vw\in E(A)$ , or (3) $vw\in E(A)$ and $xy\in E(B)$ .

Dujmović et al. [12] proved the following theorem describing the global structure of planar graphs.

Theorem 1 ([12]).

Every planar graph $G$ is isomorphic to a subgraph of $H\boxtimes P$ , for some planar graph $H$ with treewidth at most 8 and some path $P$ .

Theorem 1 has been used to solve several open problems regarding queue layouts [12], non-repetitive colourings [10], centered colourings [8], clustered colourings [11], adjacency labellings [4, 9, 13], and vertex rankings [5].

We modify the proof of Theorem 1 to establish the following.

Theorem 2.

Every planar graph $G$ is isomorphic to a subgraph of $H\boxtimes P$ , for some planar graph $H$ with simple treewidth at most 6 and some path $P$ .

Theorem 2 improves upon Theorem 1 in two respects. First it is for simple treewidth (although it should be said that the proof of Theorem 1 gives the analogous result for simple treewidth 8). The main improvement is to replace 8 by 6, which does require new ideas. The proof of Theorem 2 builds heavily on the proof of Theorem 1, which in turn builds on a result of Pilipczuk and Siebertz [19], who showed that every planar graph has a partition into geodesic paths whose contraction gives a graph with treewidth at most 8.

2 Proof of Theorem 2

Our goal is to find a given planar graph $G$ as a subgraph of $H\boxtimes P$ for some graph $H$ of small treewidth and path $P$ . Dujmović et al. [12] showed this can be done by partitioning the vertices of $G$ into so-called vertical paths in a BFS spanning tree so that contracting each path into a single vertex gives the graph $H$ (see Lemma 3 and Figure 1 below).

To formalise this idea, we need the following terminology and notation. A partition $\mathcal{P}$ of a graph $G$ is a set of connected subgraphs of $G$ , such that each vertex of $G$ is in exactly one subgraph in $\mathcal{P}$ . The quotient of $\mathcal{P}$ , denoted $G/\mathcal{P}$ , is the graph with vertex set $\mathcal{P}$ , where distinct elements $A,B\in\mathcal{P}$ are adjacent in $G/\mathcal{P}$ if there is an edge of $G$ with endpoints in $A$ and $B$ . Note that $G/\mathcal{P}$ is a minor of $G$ , so if $G$ is planar then $G/\mathcal{P}$ is planar.

If $T$ is a tree rooted at a vertex $r$ , then a non-empty path $(x_{\_}0,\dots,x_{\_}p)$ in $T$ is vertical if for some $d\geqslant 0$ for all $i\in[0,p]$ we have $\operatorname{dist}_{\_}T(x_{\_}i,r)=d+i$ .

Lemma 3 ([12]).

Let $T$ be a BFS spanning tree in a connected graph $G$ . Let $\mathcal{P}$ be a partition of $G$ into vertical paths in $T$ . Then $G$ is isomorphic to a subgraph of $(G/\mathcal{P})\boxtimes P$ , for some path $P$ .

Refer to caption — Figure 1: (a) A partition $\mathcal{P}$ of a planar graph $G$ into red vertical paths in a BFS spanning tree. (b) Illustration of $G$ as a subgraph of $(G/\mathcal{P})\boxtimes P$ .

The heart of this paper is Lemma 5 below, which is an improved version of the key lemma from [12]. The statement of Lemma 5 is identical to Lemma 13 from [12], except that we require $F$ to be partitioned into at most $5$ instead of $6$ paths and that the tree-decomposition of $H$ is 6-simple.

For a cycle $C$ , we write $C=[P_{\_}1,\dots,P_{\_}k]$ if $P_{\_}1,\dots,P_{\_}k$ are pairwise disjoint non-empty paths in $C$ , and the endpoints of each path $P_{\_}i$ can be labelled $x_{\_}i$ and $y_{\_}i$ so that $y_{\_}ix_{\_}{i+1}\in E(C)$ for $i\in[k]$ , where $x_{\_}{k+1}$ means $x_{\_}1$ . This implies that $V(C)=\bigcup_{\_}{i=1}^{k}V(P_{\_}i)$ .

The proof of Lemma 5 employs the following well-known variation of Sperner’s Lemma (see [1])

Lemma 4 (Sperner’s Lemma).

Let $G$ be a near-triangulation whose vertices are coloured $1,2,3$ , with the outerface $F=[P_{\_}1,P_{\_}2,P_{\_}3]$ where each vertex in $P_{\_}i$ is coloured $i$ . Then $G$ contains an internal face whose vertices are coloured $1,2,3$ .

Lemma 5.

Let $G^{+}$ be a plane triangulation, let $T$ be a spanning tree of $G^{+}$ rooted at some vertex $r$ on the outerface of $G^{+}$ , and let $P_{\_}1,\ldots,P_{\_}k$ for some $k\in[5]$ , be pairwise disjoint vertical paths in $T$ such that $F=[P_{\_}1,\ldots,P_{\_}k]$ is a cycle in $G^{+}$ . Let $G$ be the near-triangulation consisting of all the edges and vertices of $G^{+}$ contained in $F$ and the interior of $F$ . Then $G$ has a partition $\mathcal{P}$ into paths in $G$ that are vertical in $T$ , such that $P_{\_}1,\ldots,P_{\_}k\in\mathcal{P}$ and the quotient $H:=G/\mathcal{P}$ has a 6-simple tree-decomposition such that some bag contains all the vertices of $H$ corresponding to $P_{\_}1,\ldots,P_{\_}k$ .

Proof.

The proof is by induction on $n=|V(G)|$ . If $n=3$ , then $G$ is a 3-cycle and $k\leqslant 3$ . The partition into vertical paths is $\mathcal{P}=\{P_{\_}1,\ldots,P_{\_}k\}$ . The tree-decomposition of $H$ consists of a single bag that contains the $k\leqslant 3$ vertices corresponding to $P_{\_}1,\ldots,P_{\_}k$ . Now assume that $n>3$ .

We now set up an application of Sperner’s Lemma to the near-triangulation $G$ . We begin by colouring the vertices in $k\leqslant 5$ colours. For $i\in\{1,\ldots,k\}$ , colour each vertex in $P_{\_}i$ by $i$ . Now, for each remaining vertex $v$ in $G$ , consider the path $P_{\_}v$ from $v$ to the root of $T$ . Since $r$ is on the outerface of $G^{+}$ , $P_{\_}v$ contains at least one vertex of $F$ . If the first vertex of $P_{\_}v$ that belongs to $F$ is in $P_{\_}i$ , then assign the colour $i$ to $v$ . The set $V_{\_}i$ of all vertices of colour $i$ induces a connected subgraph of $G$ for each $i\in\{1,\ldots,k\}$ . Consider the graph $M=G/\{V_{\_}1,\ldots,V_{\_}k\}$ obtained by contracting each colour class $V_{\_}i$ into a single vertex $c_{\_}i$ . Since $G$ is planar, $M$ is planar. (In fact, $M$ is outerplanar, although we will not use this property.) Moreover, if $k\geqslant 3$ then $[c_{\_}1,\ldots,c_{\_}k]$ is a cycle in $M$ . Since $M\not\cong K_{\_}5$ , we may assume without loss of generality that either $k\leqslant 4$ or $k=5$ and $c_{\_}2c_{\_}5$ is not an edge in $M$ ; that is, no vertex coloured $2$ is adjacent to a vertex coloured $5$ .

Group consecutive paths from $P_{\_}1,\dots,P_{\_}k$ as follows:

•

If $k=1$ then, since $F$ is a cycle, $P_{\_}1$ has at least three vertices, so $P_{\_}1=[v,P_{\_}1^{\prime},w]$ for two distinct vertices $v$ and $w$ . Let $R_{\_}1:=v$ , $R_{\_}2:=P_{\_}1^{\prime}$ and $R_{\_}3:=w$ .
•

If $k=2$ then, without loss of generality, $P_{\_}1$ has at least two vertices, say $P_{\_}1=[v,P_{\_}1^{\prime}]$ . Let $R_{\_}1:=v$ , $R_{\_}2:=P_{\_}1^{\prime}$ and $R_{\_}3:=P_{\_}2$ .
•

If $k=3$ then let $R_{\_}1:=P_{\_}1$ , $R_{\_}2:=P_{\_}2$ and $R_{\_}3:=P_{\_}3$ .
•

If $k=4$ then let $R_{\_}1:=P_{\_}1$ , $R_{\_}2:=P_{\_}2$ and $R_{\_}3:=[P_{\_}3,P_{\_}4]$ .
•

If $k=5$ then let $R_{\_}1:=P_{\_}1$ , $R_{\_}2:=[P_{\_}2,P_{\_}3]$ and $R_{\_}3:=[P_{\_}4,P_{\_}5]$ .

We now derive a $3$ -colouring from the $k$ -colouring above. For $i\in\{1,2,3\}$ , colour each vertex in $R_{\_}i$ by $i$ . Now, for each remaining vertex $v$ in $G$ , consider again the path $P_{\_}v$ from $v$ to the root of $T$ and if the first vertex of $P_{\_}v$ that belongs to $F$ is in $R_{\_}i$ , then assign the colour $i$ to $v$ . Hence, for $k=3$ we obtain exactly the same 3-colouring as above, while for $k\in\{4,5\}$ some pairs of colour classes from the $k$ -colouring are merged into one colour class in the $3$ -colouring. In each case, we obtain a 3-colouring of $V(G)$ that satisfies the conditions of Lemma 4. Therefore there exists a triangular face $\tau=v_{\_}1v_{\_}2v_{\_}3$ of $G$ whose vertices are coloured $1,2,3$ respectively; see Figure 2.

For each $i\in\{1,2,3\}$ , let $Q_{\_}i$ be the path in $T$ from $v_{\_}i$ to the first ancestor $v_{\_}i^{\prime}$ of $v_{\_}i$ in $T$ that is in $F$ . Observe that $Q_{\_}1$ , $Q_{\_}2$ , and $Q_{\_}3$ are disjoint since $Q_{\_}i$ consists only of vertices coloured $i$ . Note that $Q_{\_}i$ may consist of the single vertex $v_{\_}i=v_{\_}i^{\prime}$ . Let $Q_{\_}i^{\prime}$ be $Q_{\_}i$ minus its final vertex $v_{\_}i^{\prime}$ . Imagine for a moment that the cycle $F$ is oriented clockwise, which defines an orientation of $R_{\_}1$ , $R_{\_}2$ and $R_{\_}3$ . Let $R_{\_}i^{-}$ be the subpath of $R_{\_}i$ that contains $v^{\prime}_{\_}i$ and all vertices that precede it, and let $R_{\_}i^{+}$ be the subpath of $R_{\_}i$ that contains $v^{\prime}_{\_}i$ and all vertices that succeed it.

Consider the subgraph of $G$ that consists of the edges and vertices of $F$ , the edges and vertices of $\tau$ , and the edges and vertices of $Q_{\_}1\cup Q_{\_}2\cup Q_{\_}3$ . This graph has an outerface, an inner face $\tau$ , and up to three more inner faces $F_{\_}1,F_{\_}2,F_{\_}3$ where $F_{\_}i=[Q_{\_}i^{\prime},R_{\_}i^{+},R_{\_}{i+1}^{-},Q_{\_}{i+1}^{\prime}]$ , where we use the convention that $Q_{\_}4=Q_{\_}1$ and $R_{\_}4=R_{\_}1$ . Note that $F_{\_}i$ may be degenerate in the sense that $[Q_{\_}i^{\prime},R_{\_}i^{+},R_{\_}{i+1}^{-},Q_{\_}{i+1}^{\prime}]$ may consist only of a single edge $v_{\_}iv_{\_}{i+1}$ .

Consider any non-degenerate $F_{\_}i=[Q_{\_}i^{\prime},R_{\_}i^{+},R_{\_}{i+1}^{-},Q_{\_}{i+1}^{\prime}]$ . Note that these four paths are pairwise disjoint, and thus $F_{\_}i$ is a cycle. If $Q_{\_}i^{\prime}$ and $Q_{\_}{i+1}^{\prime}$ are non-empty, then each is a vertical path in $T$ . Furthermore, each of $R_{\_}i^{+}$ and $R_{\_}{i+1}^{-}$ consists of at most two vertical paths in $T$ . Thus, $F_{\_}i$ is the concatenation of at most six vertical paths in $T$ . Let $k_{\_}i$ be the actual number of (non-empty) vertical paths whose concatenation gives $F_{\_}i$ . Then $k_{\_}1\leqslant 5$ and $k_{\_}3\leqslant 5$ since $R_{\_}1^{-}$ and $R_{\_}1^{+}$ consist of only one vertical path in $T$ . Also, if $k\leqslant 4$ then $R_{\_}2^{+}$ consists of only one vertical path in $T$ , implying $k_{\_}2\leqslant 5$ . If $k=5$ , then in our preliminary $k$ -colouring no vertex coloured $2$ is adjacent to a vertex coloured $5$ . Since $v_{\_}2v_{\_}3$ is an edge, this means that either $v_{\_}2^{\prime}$ lies on $P_{\_}3$ or $v_{\_}3^{\prime}$ lies on $P_{\_}4$ or both. In any case, at least one of $R_{\_}2^{+}$ and $R_{\_}3^{-}$ consists of only one vertical path in $T$ , which again gives $k_{\_}2\leqslant 5$ .

So $F_{\_}i$ is the concatenation of $k_{\_}i\leqslant 5$ vertical paths in $T$ for each $i\in\{1,2,3\}$ . Let $G_{\_}i$ be the near-triangulation consisting of all the edges and vertices of $G^{+}$ contained in $F_{\_}i$ and the interior of $F_{\_}i$ . Observe that $G_{\_}i$ contains $v_{\_}i$ and $v_{\_}{i+1}$ but not the third vertex of $\tau$ . Therefore $G_{\_}i$ satisfies the conditions of the lemma and has fewer than $n$ vertices. By induction, $G_{\_}i$ has a partition $\mathcal{P}_{\_}i$ into vertical paths in $T$ , such that $H_{\_}i:=G_{\_}i/\mathcal{P}_{\_}i$ has a 6-simple tree-decomposition $(B^{i}_{\_}x:x\in V(J_{\_}i))$ in which some bag $B^{i}_{\_}{u_{\_}i}$ contains the vertices of $H_{\_}i$ corresponding to the at most five vertical paths that form $F_{\_}i$ . Do this for each non-degenerate $F_{\_}i$ .

We now construct the desired partition $\mathcal{P}$ of $G$ . Initialise $\mathcal{P}:=\{P_{\_}1,\ldots,P_{\_}k\}$ . Then add each non-empty $Q_{\_}i^{\prime}$ to $\mathcal{P}$ . Now for each non-degenerate $F_{\_}i$ , classify each path in $\mathcal{P}_{\_}i$ as either external (that is, fully contained in $F_{\_}i$ ) or internal (with no vertex in $F_{\_}i$ ). Add all the internal paths of $\mathcal{P}_{\_}i$ to $\mathcal{P}$ . By construction, $\mathcal{P}$ partitions $V(G)$ into vertical paths in $T$ and $\mathcal{P}$ contains $P_{\_}1,\ldots,P_{\_}k$ .

Let $H:=G/\mathcal{P}$ . Next we construct a tree-decomposition of $H$ . Let $J$ be the tree obtained from the disjoint union of $J_{\_}i$ , taken over the $i\in\{1,2,3\}$ such that $F_{\_}i$ is non-degenerate, by adding one new node $u$ adjacent to each $u_{\_}i$ . (Recall that $u_{\_}i$ is the node of $J_{\_}i$ for which the bag $B^{i}_{\_}{u_{\_}i}$ contains the vertices of $H_{\_}i$ corresponding to the paths that form $F_{\_}i$ .) Let the bag $B_{\_}u$ contain all the vertices of $H$ corresponding to $P_{\_}1,\ldots,P_{\_}k,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ . For each non-degenerate $F_{\_}i$ , and for each node $x\in V(J_{\_}i)$ , initialise $B_{\_}x:=B^{i}_{\_}x$ . Recall that vertices of $H_{\_}i$ correspond to contracted paths in $\mathcal{P}_{\_}i$ . Each internal path in $\mathcal{P}_{\_}i$ is in $\mathcal{P}$ . Each external path $P$ in $\mathcal{P}_{\_}i$ is a subpath of $P_{\_}j$ for some $j\in[k]$ or is one of $Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ . For each such path $P$ , for every $x\in V(J)$ , in bag $B_{\_}x$ , replace each instance of the vertex of $H_{\_}i$ corresponding to $P$ by the vertex of $H$ corresponding to the path among $P_{\_}1,\ldots,P_{\_}k,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ that contains $P$ . This completes the description of $(B_{\_}x:x\in V(J))$ . By construction, $|B_{\_}x|\leqslant k+3\leqslant 8$ for every $x\in V(J)$ .

First we show that for each vertex $a$ in $H$ , the set $X:=\{x\in V(J):a\in B_{\_}x\}$ forms a subtree of $J$ . If $a$ corresponds to a path distinct from $P_{\_}1,\ldots,P_{\_}k,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ then $X$ is fully contained in $J_{\_}i$ for some $i\in\{1,2,3\}$ . Thus, by induction $X$ is non-empty and connected in $J_{\_}i$ , so it is in $J$ . If $a$ corresponds to $P$ which is one of the paths among $P_{\_}1,\ldots,P_{\_}k,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ then $u\in X$ and whenever $X$ contains a vertex of $J_{\_}i$ it is because some external path of $\mathcal{P}_{\_}i$ was replaced by $P$ . In particular, we would have $u_{\_}i\in X$ in that case. Again by induction each $X\cap J_{\_}i$ is connected and since $uu_{\_}i\in E(T)$ , we conclude that $X$ induces a (connected) subtree of $J$ .

Now we show that, for every edge $ab$ of $H$ , there is a bag $B_{\_}x$ that contains $a$ and $b$ . If $a$ and $b$ are both obtained by contracting any of $P_{\_}1,\ldots,P_{\_}k,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ , then $a$ and $b$ both appear in $B_{\_}u$ . If $a$ and $b$ are both in $H_{\_}i$ for some $i\in\{1,2,3\}$ , then some bag $B^{i}_{\_}x$ contains both $a$ and $b$ . Finally, when $a$ is obtained by contracting a path $P_{\_}a$ in $G_{\_}i-V(F_{\_}i)$ and $b$ is obtained by contracting a path $P_{\_}b$ not in $G_{\_}i$ , then the cycle $F_{\_}i$ separates $P_{\_}a$ from $P_{\_}b$ so the edge $ab$ is not present in $H$ . This concludes the proof that $(B_{\_}x:x\in V(J))$ is a tree-decomposition of $H$ . Note that $B_{\_}u$ contains the vertices of $H$ corresponding to $P_{\_}1,\dots,P_{\_}k$ .

By assumption the tree-decomposition $(B^{i}_{\_}x:x\in V(J_{\_}i))$ of $H_{\_}i$ is 6-simple for $i\in\{1,2,3\}$ . Since $|B_{\_}u\cap B_{\_}{u_{\_}i}|\leqslant 5$ for each $i\in\{1,2,3\}$ , the tree-decomposition $(B_{\_}x:x\in V(J))$ of $H$ is 6-simple, unless $|B_{\_}u|=8$ , which only occurs if $k=5$ (since $|B_{\_}u|\leqslant k+3$ ). Now assume that $k=5$ . Recall again that either $v_{\_}2^{\prime}$ lies on $P_{\_}3$ or $v_{\_}3^{\prime}$ lies on $P_{\_}4$ or both. Without loss of generality, $v_{\_}3^{\prime}$ lies on $P_{\_}4$ , and thus there is no edge between $Q_{\_}2^{\prime}$ and $P_{\_}5$ .

We now modify the above tree-decomposition of $H$ in the $k=5$ case. See Figure 3 for an illustration. First delete node $u$ from $J$ and the corresponding bag $B_{\_}u$ . Add a new node $y$ to $J$ adjacent to $u_{\_}1$ and $u_{\_}2$ , where $B_{\_}y$ consists of the vertices of $H$ corresponding to $P_{\_}1,\ldots,P_{\_}4,Q^{\prime}_{\_}1,Q^{\prime}_{\_}2,Q^{\prime}_{\_}3$ . Thus $|B_{\_}y|=7$ . Add a node $z$ to $J$ adjacent to $y$ and $u_{\_}3$ , where $B_{\_}z$ consists of the vertices of $H$ corresponding to $P_{\_}1,\dots,P_{\_}5,Q^{\prime}_{\_}1,Q^{\prime}_{\_}3$ . Thus $|B_{\_}z|=7$ and $(B_{\_}x:x\in V(J))$ is a tree-decomposition of $H$ with width 6. Since $P_{\_}5$ has no vertex in $G_{\_}1\cup G_{\_}2$ , the vertex of $H$ corresponding to $P_{\_}5$ is not in $B_{\_}{u_{\_}1}\cup B_{\_}{u_{\_}2}$ , and thus the nodes of $J$ whose bags contain this vertex form a connected subtree of $J$ . Similarly, the vertex of $H$ corresponding to $Q^{\prime}_{\_}2$ is not in $B_{\_}{u_{\_}3}$ and thus the nodes of $J$ whose bags contain this vertex form a connected subtree of $J$ . The argument for the other vertices of $H$ is identical to that above. This completes the proof that $(B_{\_}x:x\in V(J))$ is a tree-decomposition of $H$ with width at most 6. It is 6-simple since the tree-decompositions of $G_{\_}1$ , $G_{\_}2$ and $G_{\_}3$ are 6-simple, and $|B_{\_}y\cap B_{\_}{u_{\_}1}|\leqslant 5$ and $|B_{\_}y\cap B_{\_}{u_{\_}2}|\leqslant 5$ and $|B_{\_}z\cap B_{\_}{u_{\_}3}|\leqslant 5$ . Moreover, $B_{\_}z$ contains the vertices of $H$ corresponding to $P_{\_}1,\dots,P_{\_}5$ as desired. ∎

The following corollary of Lemma 5 is a direct analogue of the corresponding result in [12, Theorem 12].

Corollary 6.

Let $T$ be a rooted spanning tree in a connected planar graph $G$ . Then $G$ has a partition $\mathcal{P}$ into vertical paths in $T$ such that $\operatorname{stw}(G/\mathcal{P})\leqslant 6$ .

Proof.

The result is trivial if $|V(G)|<3$ . Now assume $|V(G)|\geqslant 3$ . Let $r$ be the root of $T$ . Let $G^{+}$ be a plane triangulation containing $G$ as a spanning subgraph with $r$ on the outerface of $G^{+}$ . The three vertices on the outerface of $G^{+}$ are vertical (singleton) paths in $T$ . Thus, $G^{+}$ satisfies the assumptions of Lemma 5 with $k=3$ and $F$ being the outerface, which implies that $G^{+}$ has a partition $\mathcal{P}$ into vertical paths in $T$ such that $\operatorname{stw}(G^{+}/\mathcal{P})\leqslant 6$ . Note that $G/\mathcal{P}$ is a subgraph of $G^{+}/\mathcal{P}$ . Hence $\operatorname{stw}(G/\mathcal{P})\leqslant 6$ . ∎

Corollaries 6 and 3 imply Theorem 2 (since we may assume that $G$ is connected).

We conclude with an open problem. Bose et al. [6] defined the row treewidth of a graph $G$ to be the minimum integer $k$ such that $G$ is isomorphic to a subgraph of $H\boxtimes P$ for some graph $H$ with treewidth $k$ and for some path $P$ . Theorem 1 by Dujmović et al. [12] says that planar graphs have row treewidth at most 8. Our Theorem 2 improves this upper bound to 6. Dujmović et al. [12] proved a lower bound of 3. In fact, they showed that for every integer $\ell$ there is a planar graph $G$ such that for every graph $H$ and path $P$ , if $G$ is isomorphic to a subgraph of $H\boxtimes P\boxtimes K_{\_}\ell$ , then $H$ contains $K_{\_}4$ and thus has treewidth at least 3. What is the maximum row treewidth of a planar graph is a tantalising open problem.

References

Aigner and Ziegler [2010] Martin Aigner and Günter M. Ziegler. Proofs from The Book. Springer, 4th edn., 2010.
Arnborg and Proskurowski [1986] Stefan Arnborg and Andrzej Proskurowski. Characterization and recognition of partial $3$ -trees. SIAM J. Algebraic Discrete Methods, 7(2):305–314, 1986.
Bodlaender [1998] Hans L. Bodlaender. A partial $k$ -arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1–45, 1998.
Bonamy et al. [2020] Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs. In Shuchi Chawla, ed., Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA ’20), pp. 446–462. 2020. arXiv:1908.03341.
Bose et al. [2020] Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, and Pat Morin. Asymptotically optimal vertex ranking of planar graphs. arXiv:2007.06455, 2020.
Bose et al. [2021] Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Separating layered treewidth and row treewidth. arXiv:2105.01230, 2021.
Chen [2016] Hao Chen. Apollonian ball packings and stacked polytopes. Discrete Comput. Geom., 55(4):801–826, 2016.
Dębski et al. [2020] Michał Dębski, Stefan Felsner, Piotr Micek, and Felix Schröder. Improved bounds for centered colorings. In Shuchi Chawla, ed., Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA ’20), pp. 2212–2226. 2020. arXiv:1907.04586.
Dujmović et al. [pear] Vida Dujmović, Louis Esperet, Gwenaël Joret, Cyril Gavoille, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). J. ACM, to appear. arXiv:2003.04280.
Dujmović et al. [2020a] Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics, 5, 2020a.
Dujmović et al. [2021] Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. Clustered 3-colouring graphs of bounded degree. Combinatorics, Probability & Computing, 2021. arXiv:2002.11721.
Dujmović et al. [2020b] Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM, 67(4):22, 2020b.
Esperet et al. [2020] Louis Esperet, Gwenaël Joret, and Pat Morin. Sparse universal graphs for planarity. 2020. arXiv:2010.05779.
Frieze and Tsourakakis [2014] Alan Frieze and Charalampos E. Tsourakakis. Some properties of random Apollonian networks. Internet Math., 10(1-2):162–187, 2014.
Harvey and Wood [2017] Daniel J. Harvey and David R. Wood. Parameters tied to treewidth. J. Graph Theory, 84(4):364–385, 2017.
Knauer and Ueckerdt [2012] Kolja Knauer and Torsten Ueckerdt. Simple treewidth. In Pavel Rytír, ed., Midsummer Combinatorial Workshop Prague. 2012.
Kratochvíl and Vaner [2012] Jan Kratochvíl and Michal Vaner. A note on planar partial 3-trees. arXiv:1210.8113, 2012.
Markenzon et al. [2006] Lilian Markenzon, Claudia Marcela Justel, and N. Paciornik. Subclasses of $k$ -trees: characterization and recognition. Discrete Appl. Math., 154(5):818–825, 2006.
Pilipczuk and Siebertz [2019] Michał Pilipczuk and Sebastian Siebertz. Polynomial bounds for centered colorings on proper minor-closed graph classes. In Timothy M. Chan, ed., Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1501–1520. 2019. arXiv:1807.03683.
Reed [2003] Bruce A. Reed. Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, vol. 11, pp. 85–107. Springer, 2003.
Robertson and Seymour [1986] Neil Robertson and Paul Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986.
Wulf [2016] Lasse Wulf. Stacked treewidth and the Colin de Verdiére number. 2016. Bachelorthesis, Institute of Theoretical Computer Science, Karlsruhe Institute of Technology.