Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar graphs is NP-complete w.r.t to the number of vertices per David Eppstein[1].
However, the MCS of partial k-Trees of Bounded degree, (including outerplanar graphs, etc.), can be evaluated in polynomial time [2].
Is there a result for something in-between? Practical answers are also welcome.
[1] Largest common subgraph of two maximal planar graphs
[2] http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1