A Fast Algorithm for the Product Structure of Planar Graphs
share
Dujmović et al (FOCS2019) recently proved that every planar graph G is a subgraph of H P, where 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 P). In this note, we show that this algorithm can be made to run in O(nlog n) time.
READ FULL TEXT