论文标题
有效地识别平面立方无桥图的子图
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
论文作者
论文摘要
从泰特（Tait）的工作和四色理论上的工作来看，平面立方图在且仅当它不包含桥梁时才可以3边色彩。我们考虑了哪些平面图是平面立方无桥图的子图，因此3边色。我们提供了一种有效的识别算法，给出了$ n $ vertex平面图，以$ o（n^2）$步骤将此图扩大到平面立方体bridgeless Supergraph，或者决定不可能进行这种增强。主要工具涉及固定嵌入情况的广义抗乳清问题，以及用于可变嵌入情况的SPQR-Trees。
It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an $n$-vertex planar graph, augments this graph in $O(n^2)$ steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized Antifactor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.
