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 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. 
Chris Dowden, Louigi Addario-Berry
math.CO