Subgraphs of 4-Regular Planar Graphs
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 GaS integral 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.
planar graphs subgraph appearance