<p>This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See <a href="http://arxiv.org/abs/1203.5944">http://arxiv.org/abs/1203.5944</a> </p>

CC BY-SA 3.0
2012-09-03T20:27:43.610Z
"A graph is near-planar if it can be obtained from a planar graph by adding an edge. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar." I must be missing something.  Why isn't every near-planar graph also 1-planar?
Tyson Williams
CC BY-SA 3.0
2012-09-04T03:36:35.063Z
What I think you're saying is that you can just take a planar embedding of $G-e$ and add the edge back in. However, that extra edge could cross more than one edge, violating 1-planarity.
Timothy Sun
CC BY-SA 3.0
2012-09-04T12:36:53.307Z
@TimothySun Yes.  Every edge other than $e$ will be crossed at most once (by $e$), but $e$ could be crossed by more than one other edge, which is not allowed. Thanks.
Tyson Williams
CC BY-SA 3.0
2012-09-03T18:02:59.230Z
2012-09-03T18:02:59.230Z
someone
<p>If toy problems are fine:</p>

<p>Let $g\in\mathbb{N}$ and let $H$ be some graph of genus $g+1$. For $\phi$ a CNF-formula, let $G_\phi$ be some encoding of $\phi$ as a planar graph <em>plus</em> a disjoint copy of $H$.</p>

<p>Given $G_\phi$, which is a graph of genus $g+1$, it is NP-hard to decide whether $\phi$ is satisfiable. This problem however becomes trivial when restricted to graphs of genus $\leq g$.</p>

CC BY-SA 3.0
2012-09-05T01:14:23.873Z
what is this problem on graphs of genus $\leq g$
Sasho Nikolov
CC BY-SA 3.0
2012-09-05T09:12:38.440Z
All graphs $G_\phi$ have genus $g+1$. Thus, if you restrict the problem to graphs of genus $g$, you can always reject.
Radu Curticapean
CC BY-SA 3.0
2012-09-05T16:14:33.313Z
ah, it becomes *really* trivial, I see
Sasho Nikolov
CC BY-SA 3.0
2012-09-04T21:09:45.517Z
2012-09-04T21:09:45.517Z
Radu Curticapean
<p>For any fixed&nbsp;$g$, there is a polynomial-time algorithm to determine whether a graph has genus (at most)&nbsp;$g$.  Let $X_g$&nbsp; be any problem that is NP-complete on graphs of genus greater than&nbsp;$g$ (e.g., 3-colourability).  For each fixed&nbsp;$g$, the problem "Does the input graph have genus at most&nbsp;$g$ or is it in&nbsp;$X_g$ (or both)?" is NP-complete for general input but has a polynomial-time algorithm when the input is restricted to graphs of genus at most&nbsp;$g$.</p>

<p>This idea can be used quite generally to produce problems that are "hard" on general graphs but "easy" on some class&nbsp;$\mathcal C$ of graphs, as long as it is "easy" to determine membership in&nbsp;$\mathcal C$.</p>

CC BY-SA 3.0
2013-07-26T12:59:30.570Z
2013-07-26T12:59:30.570Z
David Richerby
<p><strong>EDIT (2012-09-05):</strong> Jeff's and Radu's comments are right. The cited result does not answer the question. To expand on Radu's comment, here is a related algorithm by <a href="http://arxiv.org/pdf/1008.0683.pdf" rel="nofollow">Bravyi</a> which gives an algorithm for contracting matchgate tensors on a graph $G$ with genus $g$ with run-time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar. </p>

<hr>

<p><a href="http://arxiv.org/pdf/1008.0683.pdf" rel="nofollow">Cai, Lu, and Xia</a> recently proved the following dichotomy for #CSP counting problems:</p>

<blockquote>
  <p>We prove complexity dichotomy theorems in the framework of counting
  CSP problems. The local constraint functions take Boolean inputs, and
  can be arbitrary real-valued symmetric functions. We prove that, every
  problem in this class belongs to precisely three categories: </p>
  
  <p>(1) those which are tractable (i.e., polynomial time computable) on
  general graphs, or<br>
  (2) those which are <strong>#P-hard on general graphs but
  tractable on planar graphs</strong>, or<br>
  (3) those which are #P-hard even on
  planar graphs. </p>
  
  <p>The classication criteria are explicit.</p>
</blockquote>

CC BY-SA 3.0
2012-09-04T22:45:49.037Z
This doesn't answer the question.  Can category (2) can be split into (2a) tractable for planar graphs but #P-hard for toroidal graphs, and (2b) tractable for bounded-genus graphs but #P-hard for unbounded-genus graphs?
Jeffε
CC BY-SA 3.0
2012-09-04T23:42:44.213Z
Case (2) consists of problems that can be reduced to counting perfect matchings in planar graphs by introducing local planar gadgets. It is [also known](http://www.combinatorics.org/Volume_6/PDF/v6i1r6.pdf) that perfect matchings can be counted in polynomial time on bounded-genus graphs. Thus, _all_ problems in case (2) are actually tractable on bounded-genus graphs.
Radu Curticapean
CC BY-SA 3.0
2012-09-04T21:59:59.953Z
2012-09-05T08:35:30.517Z
2012-09-05T08:35:30.517Z
Martin Schwarz
<p>Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :</p>

<ul>
<li><p>Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?</p></li>
<li><p>More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?</p></li>
</ul>

CC BY-SA 3.0
2012-09-03T22:05:06.350Z
For the second question, do you want the problem to be NP-hard for graphs of genus >= k, where k is a constant greater than g? OR do you just want the problem to be NP-hard for graphs whose genus isn't less than g (which is equivalent to it being NP-hard for general graphs)?
Robin Kothari
CC BY-SA 3.0
2012-09-04T06:14:41.073Z
I am looking for NP-Hard problems for graphs of genus >= k, where k is a constant greater than g.
Shiva Kintali
<cc.complexity-theory><ds.algorithms><graph-theory><planar-graphs>
Hard Problems for higher genus graphs
Shiva Kintali
# Hard Problems for higher genus graphs

(Asked by: username_0 on 2012-09-03)

Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :

* Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?
* More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, planar-graphs
> **Comments:**
> **username_1**: For the second question, do you want the problem to be NP-hard for graphs of genus >= k, where k is a constant greater than g? OR do you just want the problem to be NP-hard for graphs whose genus isn't less than g (which is equivalent to it being NP-hard for general graphs)?  
> **username_0**: I am looking for NP-Hard problems for graphs of genus >= k, where k is a constant greater than g.  

---

## 4 answers

### Answer by username_2 on 2012-09-03. Score: 16

This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See <http://arxiv.org/abs/1203.5944>

> **Comments:**
> **username_3**: "A graph is near-planar if it can be obtained from a planar graph by adding an edge. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar." I must be missing something.  Why isn't every near-planar graph also 1-planar?  
> **username_4**: What I think you're saying is that you can just take a planar embedding of $G-e$ and add the edge back in. However, that extra edge could cross more than one edge, violating 1-planarity.  
> **username_3**: @TimothySun Yes.  Every edge other than $e$ will be crossed at most once (by $e$), but $e$ could be crossed by more than one other edge, which is not allowed. Thanks.  

---

### Answer by username_5 on 2012-09-04. Score: 5

If toy problems are fine:

Let $g\in\mathbb{N}$ and let $H$ be some graph of genus $g+1$. For $\phi$ a CNF-formula, let $G\_\phi$ be some encoding of $\phi$ as a planar graph *plus* a disjoint copy of $H$.

Given $G\_\phi$, which is a graph of genus $g+1$, it is NP-hard to decide whether $\phi$ is satisfiable. This problem however becomes trivial when restricted to graphs of genus $\leq g$.

> **Comments:**
> **username_6**: what is this problem on graphs of genus $\leq g$  
> **username_5**: All graphs $G_\phi$ have genus $g+1$. Thus, if you restrict the problem to graphs of genus $g$, you can always reject.  
> **username_6**: ah, it becomes *really* trivial, I see  

---

### Answer by username_7 on 2013-07-26. Score: 3

For any fixed $g$, there is a polynomial-time algorithm to determine whether a graph has genus (at most) $g$. Let $X\_g$  be any problem that is NP-complete on graphs of genus greater than $g$ (e.g., 3-colourability). For each fixed $g$, the problem "Does the input graph have genus at most $g$ or is it in $X\_g$ (or both)?" is NP-complete for general input but has a polynomial-time algorithm when the input is restricted to graphs of genus at most $g$.

This idea can be used quite generally to produce problems that are "hard" on general graphs but "easy" on some class $\mathcal C$ of graphs, as long as it is "easy" to determine membership in $\mathcal C$.


---

### Answer by username_8 on 2012-09-04. Score: 2

**EDIT (2012-09-05):** Jeff's and Radu's comments are right. The cited result does not answer the question. To expand on Radu's comment, here is a related algorithm by [Bravyi](http://arxiv.org/pdf/1008.0683.pdf) which gives an algorithm for contracting matchgate tensors on a graph $G$ with genus $g$ with run-time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar.

---

[Cai, Lu, and Xia](http://arxiv.org/pdf/1008.0683.pdf) recently proved the following dichotomy for #CSP counting problems:

> We prove complexity dichotomy theorems in the framework of counting
> CSP problems. The local constraint functions take Boolean inputs, and
> can be arbitrary real-valued symmetric functions. We prove that, every
> problem in this class belongs to precisely three categories:
>
> (1) those which are tractable (i.e., polynomial time computable) on
> general graphs, or  
> (2) those which are **#P-hard on general graphs but
> tractable on planar graphs**, or  
> (3) those which are #P-hard even on
> planar graphs.
>
> The classication criteria are explicit.

> **Comments:**
> **username_9**: This doesn't answer the question.  Can category (2) can be split into (2a) tractable for planar graphs but #P-hard for toroidal graphs, and (2b) tractable for bounded-genus graphs but #P-hard for unbounded-genus graphs?  
> **username_5**: Case (2) consists of problems that can be reduced to counting perfect matchings in planar graphs by introducing local planar gadgets. It is [also known](http://www.combinatorics.org/Volume_6/PDF/v6i1r6.pdf) that perfect matchings can be counted in polynomial time on bounded-genus graphs. Thus, _all_ problems in case (2) are actually tractable on bounded-genus graphs.  

---

