4
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.