<p>Are there any known (natural) problems that are polynomial time solvable on planar graphs, but NP-complete on toroidal graphs?</p>
<p>I'm not looking for problems like 4-Coloring, Planar Vertex Deletion, Crossing Number, or other problems that are &quot;always true&quot; on planar graphs due to structural reasons.</p>

CC BY-SA 4.0
2024-06-26T13:48:43.807Z
This was already asked with some useful answers/discussion. See https://cstheory.stackexchange.com/questions/12490/hard-problems-for-higher-genus-graphs
Chandra Chekuri
CC BY-SA 4.0
2024-06-26T20:15:45.103Z
Thank you very much, @ChandraChekuri, I didn't find that question.  I think the question is still interesting, almost 12 years later, and it seems like the answer to the question is _no_.
John K.
<np-hardness><planar-graphs>
Problems hard on toroidal graphs that are polytime on planar
John K.
# Problems hard on toroidal graphs that are polytime on planar

(Asked by: username_0 on 2024-06-25)

Are there any known (natural) problems that are polynomial time solvable on planar graphs, but NP-complete on toroidal graphs?

I'm not looking for problems like 4-Coloring, Planar Vertex Deletion, Crossing Number, or other problems that are "always true" on planar graphs due to structural reasons.

**Tags:** np-hardness, planar-graphs
> **Comments:**
> **username_1**: This was already asked with some useful answers/discussion. See https://cstheory.stackexchange.com/questions/12490/hard-problems-for-higher-genus-graphs  
> **username_0**: Thank you very much, @ChandraChekuri, I didn't find that question.  I think the question is still interesting, almost 12 years later, and it seems like the answer to the question is _no_.  

---

## 0 answers

