Subgraphs of 4-regular planar graphs
arXiv:1101.5294 · doi:10.1007/s00453-010-9435-8
Abstract
We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^{2.5}) and can be used to find an explicit 4-regular planar graph G containing H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.
21 pages, 19 figures. To be published in Algorithmica