论文标题
平面图中产品结构的最佳算法
An Optimal Algorithm for Product Structure in Planar Graphs
论文作者
论文摘要
平面图的\ emph {fords结构定理}（Dujmović等人。我们提供了一种简单的线性时间算法，用于查找该分解以及几个相关的分解。这在前一个$ o（n \ log n）$ time算法（morin。
The \emph{Product Structure Theorem} for planar graphs (Dujmović et al.\ \emph{JACM}, \textbf{67}(4):22) states that any planar graph is contained in the strong product of a planar $3$-tree, a path, and a $3$-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous $O(n\log n)$ time algorithm (Morin.\ \emph{Algorithmica}, \textbf{85}(5):1544--1558).
