<p><strong>Cubic Montone Planar 1-in-3 SAT</strong>:
<a href="http://en.wikipedia.org/wiki/One-in-three_3SAT" rel="nofollow">1-in-3 SAT</a> without negated variables and where each variable is in exactly 3 clauses, and the incidence graph (the bipartite graph where the variables and the clauses are the vertex sets) is planar.</p>

<p><a href="http://arxiv.org/abs/math/0003039" rel="nofollow">http://arxiv.org/abs/math/0003039</a></p>

<p>If you are willing to relax the 3-regularity, this may be relevant: <strong>Planar-3-Connected (3,4)-SAT</strong>, 3SAT but where each variable is in at most 4 clauses, and the incidence graph is polyhedral (3-connected and planar).</p>

<p><a href="http://dx.doi.org/10.1016/0166-218X(94)90143-0" rel="nofollow">http://dx.doi.org/10.1016/0166-218X(94)90143-0</a></p>

CC BY-SA 3.0
2011-11-05T05:48:40.087Z
2011-11-05T18:18:54.597Z
2011-11-05T18:18:54.597Z
didest
<p>Does subclass mean a class of subgraphs? If yes:</p>

<p>In holographic algorithms, $(2,3)$-regular bipartite graphs are studied, i.e., the nodes on the lefthand side have degree 2 and on the righthand side have degree 3. The <a href="http://arxiv.org/abs/1001.0464" rel="nofollow">dichotomy theorems</a> by Kowalczyk and Cai (STACS 2010) yield hard problems for such graphs.</p>

CC BY-SA 3.0
2011-04-11T19:34:22.100Z
No, subclass is not a class of subgraphs. Here it means a restricted class of planar cubic bipartite graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-11T19:27:33.217Z
2011-09-16T14:53:22.247Z
2011-09-16T14:53:22.247Z
5501
<p>Nick Wormald: Models of random regular graphs in Surveys in COmbinatorics, London Math Society
Lecture Notes Series, 276 Cambridge University Press, 1999, 239-298, 1999</p>

CC BY-SA 3.0
2011-04-14T22:15:25.933Z
Hi Josep, I'm not sure if this answers the question.  Random cubic graphs aren't necessarily planar nor are they bipartite.  I couldn't find a good online version of this article and MathSciNet does not mention anything about conditioning on either of the abovementioned properties...  Could you please clarify?
RJK
CC BY-SA 3.0
2011-04-12T08:42:39.367Z
2011-04-12T08:42:39.367Z
josep
<p>Hamiltonicity <a href="http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/sub/j/DVD/PDF_J/J029.pdf">remains NP-complete</a> for 2-vertex-connected cubic planar bipartite graphs, but this is not actually a restriction: every cubic planar bipartite graph is 2-connected. It is <a href="http://en.wikipedia.org/wiki/Barnette%27s_conjecture">a well-known open problem</a> whether 3-connected cubic planar bipartite graphs always have Hamiltonian cycles, but if they do not then the problem is NP-complete for them as well.</p>

<p>(<a href="http://arxiv.org/abs/0912.0537">One of my recent papers</a> looked at some related connectivity classes of cubic planar bipartite graphs but not from the point of view of NP-hardness.)</p>

CC BY-SA 3.0
2011-04-12T06:29:41.183Z
Thanks David. Could you please point me to a reference that surveys different characterizations of planar cubic bipartite graphs and how to generate them. I'm aware of a characterization of planar bipartite graphs in terms of contact graphs of vertical and horizontal line segments.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-12T21:22:29.483Z
Don't know of such a reference, sorry.
David Eppstein
CC BY-SA 3.0
2011-04-11T23:55:52.923Z
2011-04-12T01:20:46.343Z
2011-04-12T01:20:46.343Z
David Eppstein
<p>Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses of planar cubic bipartite graphs. An interesting subclass contains infinite number of graphs and excludes infinite number of graphs. </p>

<p>More importantly, Which hard problems do remain hard on nontrivial subclasses of planar cubic bipartite graphs?</p>

<cc.complexity-theory><reference-request><graph-classes>
Hard problems on subclasses of planar cubic bipartite graphs
Mohammad Al-Turkistany
# Hard problems on subclasses of planar cubic bipartite graphs

(Asked by: username_0 on 2011-04-11)

Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses of planar cubic bipartite graphs. An interesting subclass contains infinite number of graphs and excludes infinite number of graphs.

More importantly, Which hard problems do remain hard on nontrivial subclasses of planar cubic bipartite graphs?

**Tags:** cc.complexity-theory, reference-request, graph-classes


---

## 4 answers

### Answer by username_5 on 2011-04-11. Score: 10 | Accepted answer

Hamiltonicity [remains NP-complete](http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/sub/j/DVD/PDF_J/J029.pdf) for 2-vertex-connected cubic planar bipartite graphs, but this is not actually a restriction: every cubic planar bipartite graph is 2-connected. It is [a well-known open problem](http://en.wikipedia.org/wiki/Barnette%27s_conjecture) whether 3-connected cubic planar bipartite graphs always have Hamiltonian cycles, but if they do not then the problem is NP-complete for them as well.

([One of my recent papers](http://arxiv.org/abs/0912.0537) looked at some related connectivity classes of cubic planar bipartite graphs but not from the point of view of NP-hardness.)

> **Comments:**
> **username_0**: Thanks David. Could you please point me to a reference that surveys different characterizations of planar cubic bipartite graphs and how to generate them. I'm aware of a characterization of planar bipartite graphs in terms of contact graphs of vertical and horizontal line segments.  
> **username_5**: Don't know of such a reference, sorry.  

---

### Answer by username_1 on 2011-11-05. Score: 3

**Cubic Montone Planar 1-in-3 SAT**:
[1-in-3 SAT](http://en.wikipedia.org/wiki/One-in-three_3SAT) without negated variables and where each variable is in exactly 3 clauses, and the incidence graph (the bipartite graph where the variables and the clauses are the vertex sets) is planar.

<http://arxiv.org/abs/math/0003039>

If you are willing to relax the 3-regularity, this may be relevant: **Planar-3-Connected (3,4)-SAT**, 3SAT but where each variable is in at most 4 clauses, and the incidence graph is polyhedral (3-connected and planar).

<http://dx.doi.org/10.1016/0166-218X(94)90143-0>


---

### Answer by username_2 on 2011-04-11. Score: 3

Does subclass mean a class of subgraphs? If yes:

In holographic algorithms, $(2,3)$-regular bipartite graphs are studied, i.e., the nodes on the lefthand side have degree 2 and on the righthand side have degree 3. The [dichotomy theorems](http://arxiv.org/abs/1001.0464) by Kowalczyk and Cai (STACS 2010) yield hard problems for such graphs.

> **Comments:**
> **username_0**: No, subclass is not a class of subgraphs. Here it means a restricted class of planar cubic bipartite graphs.  

---

### Answer by username_3 on 2011-04-12. Score: 0

Nick Wormald: Models of random regular graphs in Surveys in COmbinatorics, London Math Society
Lecture Notes Series, 276 Cambridge University Press, 1999, 239-298, 1999

> **Comments:**
> **username_4**: Hi Josep, I'm not sure if this answers the question.  Random cubic graphs aren't necessarily planar nor are they bipartite.  I couldn't find a good online version of this article and MathSciNet does not mention anything about conditioning on either of the abovementioned properties...  Could you please clarify?  

---

