<p>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.</p>

CC BY-SA 3.0
2016-05-24T07:19:41.540Z
2016-05-24T07:19:41.540Z
Saeed
<p>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].</p>

<p>However, the MCS of partial k-Trees of Bounded degree, (including outerplanar graphs, etc.), can be evaluated in polynomial time [2].</p>

<p>Is there a result for something in-between? Practical answers are also welcome.</p>

<p>[1] <a href="https://cstheory.stackexchange.com/questions/6095/largest-common-subgraph-of-two-maximal-planar-graphs">Largest common subgraph of two maximal planar graphs</a></p>

<p>[2] <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1" rel="nofollow noreferrer">http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1</a></p>

<ds.algorithms><graph-theory><graph-isomorphism>
Maximum common subgraph of two planar graphs of bounded degree k
Michael Davis
# Maximum common subgraph of two planar graphs of bounded degree k

(Asked by: username_0 on 2016-05-21)

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](https://cstheory.stackexchange.com/questions/6095/largest-common-subgraph-of-two-maximal-planar-graphs)

[2] <http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1>

**Tags:** ds.algorithms, graph-theory, graph-isomorphism


---

## 1 answers

### Answer by username_1 on 2016-05-24. Score: 6

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.


---

