# Maximum common subgraph of two planar graphs of bounded degree k

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.

Maybe I misunderstood the question, but it seems it's NPC and this is trivial. Finding hamiltonian cycle in planar graphs of max degree $3$ is NPC. Therefore this problem is also NPC (input: A planar graph of max degree $3$ on $n$ vertices and a cycle on $n$ vertex.