A Fast Algorithm for the Product Structure of Planar Graphs

Dujmović et al. (FOCS2019) recently proved that every planar graph G is a subgraph of \(H\boxtimes P\), where \(\boxtimes\) denotes the strong graph product, H is a graph of treewidth 8 and P is a path. This result has found numerous applications to linear graph layouts, graph colouring, and graph labelling. The proof given by Dujmović et al. is based on a similar decomposition of Pilipczuk and Siebertz (SODA2019) which is constructive and leads to an \(O(n^2)\) time algorithm for finding H and the mapping from V(G) onto \(V(H\boxtimes P)\). In this note, we show that this algorithm can be made to run in \(O(n\log n)\) time.

1. The length of a path is equal to the number of edges in the path, which is one less than the number of vertices in the path.

2. A data structure supporting these two operations in O(1) amortized time per operation can be obtained from the work of Gabow and Tarjan [8], but the data structure described in Appendix A is considerably simpler to implement and is fast enough for our purposes.

Part of this research was conducted during the Eighth Workshop on Geometry and Graphs, held at the Bellairs Research Institute, January 31–February 7, 2020. The author is grateful to the other organizers and participants for providing a stimulating research environment. The author would like to thank Vida Dujmović and our summer student Ivana Marusic. Ivana implemented the algorithm described in Sect. 2 and the algorithm described in Sect. 3. The second implementation motivated the development of the simple nearest marked ancestor data structure in Appendix A. This research was partially supported by NSERC.

Authors and Affiliations

1. School of Computer Science, Carleton University, Ottawa, Canada

   Pat Morin

Corresponding author

Correspondence to Pat Morin.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Data Structures

In this appendix we describe the simple data structures used by our algorithm. Devising these data structures is an exercise in the use of two standard techniques (a simple union-find data structure and the interval labelling scheme for rooted trees).

1.1 A.1: Interval Splitting

An interval splitting data structure stores an initially-empty subset S of \(\{1,\ldots ,n\}\) under the following two operations, each of which takes an integer argument \(x\in \{1,\ldots ,n\}\):

• \(\textsc {Add}(x)\): Add x to the set S, i.e., \(S\leftarrow S\cup \{x\}\). It is a precondition of this operation that \(x\not \in S\).

• \(\textsc {Interval}(x)\): Return the pair (i, j) where \(i=\max \{y\in S\cup \{0\}:y<x\}\) and \(j=\min \{y\in S\cup \{n+1\}:y\geqslant x\}\).

Lemma 6

There exists a data structure that preprocesses an integer n and supports the \(\textsc {Add}(x)\) and \(\textsc {Interval}(x)\) operations. The data structures uses O(n) preprocessing time, each \(\textsc {Interval}(x)\) operation runs in O(1) time and any sequence of \(\textsc {Add}(x)\) operations takes a total of \(O(n\log n)\) time.

Proof

The data structure is essentially the inverse of one of the simplest union-find data structures that represents sets as linked lists in which each node has a pointer to the head of the list.

The data structure contains an array \(a_1,\ldots ,a_n\) of pointers. For each \(x\in \{1,\ldots ,n\}\), the array entry \(a_x\) points to a memory location m storing the interval (i, j) that answers the \(\textsc {Interval}(x)\) query. In this way each \(\textsc {Interval}(x)\) query operation runs in O(1) time, as required.

The data structure is memory-efficient in the following sense: Suppose that, at some point in time \(S=\{x_1,\ldots ,x_k\}\) with \(x_1<\cdots <x_k\). and use the convention that \(x_0:=0\) and \(x_{k+1}=n+1\). Then, for each \(i\in \{0,\ldots ,k\}\), the array locations \(a_{x_{i}+1},\ldots ,a_{\min \{n,x_{i+1}\}}\) all point the same memory location m that contains the pair (i, j), \(i<x\leqslant j\) that answers the \(\textsc {Interval}(x)\) query for each value \(x\in \{x_{i}+1,\ldots ,x_{i+1}\}\). Thus, the number of distinct memory locations m used to store answers to \(\textsc {Interval}(x)\) queries is exactly \(k+1\).

To perform an \(\textsc {Add}(x)\) operation, the data structure first looks at the pair (i, j) stored at the memory location m referenced by \(a_x\). Observe that the \(j-i\) array entries \(a_{i+1},\ldots ,a_{j}\) all point to the same memory location m and let \(k:=x-i\). The data structure allocates a new memory location \(m'\) containing a pair \((i',j')\). The algorithm then makes a choice, depending on the value of k.

1. 1.

   If \(k\leqslant (j-i)/2\), then it sets \((i',j')\leftarrow (i,x)\), sets \((i,j)\leftarrow (x,j)\) and sets \(a_{i+1},\ldots ,a_{x}\leftarrow m'\).

2. 2.

   Otherwise, it sets \((i',j')\leftarrow (x,j)\), sets \((i,j)\leftarrow (i,x)\) and sets \(a_{x+1},\ldots ,a_{j}\leftarrow m'\).

It is straightforward to verify that these operations are correct.

To analyze total running time of a sequence of \(\textsc {Add}(x)\) operations, we use the potential method of amortized analysis. For each \(\ell \in \{1,\ldots ,n\}\), let \(\Phi _\ell =c\log _2(j-i)\) where (i, j) is the answer to \(\textsc {Interval}(\ell )\) and let \(\Phi =\sum _{\ell =1}^n \Phi _\ell\). Observe that \(0\leqslant \Phi _\ell \leqslant c\log _2(n+1)\) for each \(\ell \in \{1,\ldots ,n\}\), so \(0\leqslant \Phi \leqslant cn\log _2(n+1)\). Note, furthermore that the \(\textsc {Interval}(x)\) operation has no effect on \(\Phi\).

When an \(\textsc {Add}(x)\) operation runs, it updates some number z of array entries (either \(z=k\) or \(z=j-i-k\). This takes O(z) time and does not cause \(\Phi _\ell\) to increase for any \(\ell \in \{1,\ldots ,n\}\). Furthermore, this operation causes \(\Phi _\ell\) to decrease by at least c for each array entry \(a_\ell\) that is modified. Therefore, letting \(\Phi\) and \(\Phi '\) denote the value of \(\Phi\) before and after this operation, we have \(\Phi '-\Phi \leqslant -cz\). The amortized running time of this operation is therefore \(O(1+z+\Phi '-\Phi ) = O(1)\) for a sufficiently large constant c.

Therefore each \(\textsc {Add}(x)\) operation runs in O(1) amortized time, the minimum potential is 0 and the maximum potential is \(cn\log _2(n+1)\), so the total running time of any sequence of \(\textsc {Add}(x)\) operations is at most \(O(m + n\log n)\). The precondition that \(x\not \in S\) ensures that \(m\leqslant n\), so the total running time is \(O(n\log n)\). \(\square\)

1.2 A.2: Nearest Marked Ancestor

Proof of Lemma 4

The data structure is essentially the interval labelling scheme for trees combined with the interval splitting data structure from the previous section.

Let \(T'\) be the directed graph obtained by replacing each undirected edge vw of T with two directed edges vw and wv. Since every node of \(T'\) has the same in and out degree, it is Eulerian. Let \(v_1,v_2,\ldots ,v_{2n-1}\) be the sequence of vertices encountered during an Euler tour of \(T'\) that begins and ends at the root \(v_1=v_{2n-1}\) of T. For each node v of T, let \(i_v:=\min \{i:v_i=v\}\) and \(j_v:=\max \{j:v_j=v\}\). Observe that \(v_{i_v},v_{i_v+1},\ldots ,v_{j_v}\) contains exactly those nodes of T that have v as a T-ancestor.

The data structure stores the sequence \(v_0,v_1,v_2,\ldots ,v_{2n-1}\) in an array and maintains an interval splitting data structure on the set \(1,\ldots ,2n-1\). The operation of \(\textsc {Mark}(w)\) is simple: We simply call \(\textsc {Add}(i_w)\) and \(\textsc {Add}(j_w)\). Note that the precondition that \(w\not \in S\) ensures that the precondition \(x\not \in S\) of the \(\textsc {Add}(x)\) operation is satisified. Thus, any sequence of \(\textsc {Mark}(w)\) operations results in a sequence of \(\textsc {Add}(x)\) operations on the set \(\{1,\ldots ,2n-1\}\). By Lemma 6 this takes a total of \(O(n\log n)\) time, as required.

The operation of the \(\textsc {NearestMarkedAncestor}(v)\) is almost as simple. We call \(\textsc {Interval}(i_w)\) to obtain some pair (i, j) with \(i< i_w \leqslant j\). There are two cases to consider:

1. 1.

   If \(j=i_w\) then this is because \(w\in S\), in which case w is the nearest marked ancestor of itself.

2. 2.

   Otherwise, \(i<i_w<j\), and \((i,j)=(i_v,j_v)\) for some node \(v\in S\). Therefore, \(v_{i}=v_{j}\) is the nearest marked ancestor of w.

Therefore, in either case, we obtain the nearest marked ancestor of w in O(1) time, as required. \(\square\)

Reprints and permissions