<p>The classic <a href="http://epubs.siam.org/doi/abs/10.1137/0211025" rel="nofollow noreferrer">reduction from 3SAT to PLANAR-3SAT</a> requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the <a href="https://en.wikipedia.org/wiki/Crossing_number_inequality" rel="nofollow noreferrer">crossing number inequality</a> suggests that it may not be necessary to have that many crossings.</p>

<p>Is there a way to reduce 3SAT to PLANAR-3SAT in time $O(m^{2-\varepsilon})$ with $\varepsilon&gt;0$ (or less) for subclasses of 3SAT (e.g., read-(at most)-$r$ 3SAT with bounded $r$)?</p>

CC BY-SA 3.0
2018-02-04T04:45:02.793Z
I believe such a reduction would refute ETH, using fast exptime algorithms for planar-3sat. (If we are defining planar-3sat in terms of the "clause-clause" graph.)
Ryan Williams
CC BY-SA 3.0
2018-02-04T17:45:25.920Z
@RyanWilliams Indeed. I know refuting ETH is a tall order, but the bipartite graphs related to 3SAT have limitations in their degree sequences, especially if appearance of variables is restricted. The crossing number lemma leaves room for subclasses of these graphs to have a crossing number in $o(m^2)$. I now restrict the question to subclasses of 3SAT, as this is slightly more likely.
delete000
CC BY-SA 3.0
2018-02-04T21:11:54.530Z
For SAT instances with $O(n)$ clauses the "sufficuently many edges compared to vertices" of the crossing number inequality does not hold. For instances with a superlinear number of clauses, applying the sparsification lemma and then then the standard reduction does the job.
daniello
CC BY-SA 3.0
2018-02-04T23:00:16.777Z
@daniello For 3SAT instances with $n$ variables and $m$ clauses, if we fix $\alpha=m/n=4$, then we have that the number of edges is $e=3m=3 \alpha n = 12n$, which fulfills the requirement $e>4n$ for the crossing number lemma to hold. Am I missing something?
delete000
CC BY-SA 3.0
2018-02-05T03:52:17.300Z
The part about the crossing number inequality in my previous comment is nonsense. In fact the crossing number inequality is in the wrong direction to have any bearing on this question - it *lower bounds* the number of crossings, and the bound is not tight for graphs with a linear number of edges. Indeed, 3-regular expanders need $\Omega(n^2)$ crossings.
daniello
CC BY-SA 3.0
2018-02-05T12:39:40.463Z
@daniello Thanks. I found a related question on MO with relevant references that may be helpful to anyone stumbling on this one: https://mathoverflow.net/questions/182404/do-there-exist-sparse-graphs-with-large-crossing-number
delete000
<cc.complexity-theory><graph-theory><reductions><polynomial-time><boolean-formulas>
Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$
delete000
# Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$

(Asked by: username_0 on 2018-02-04)

The classic [reduction from 3SAT to PLANAR-3SAT](http://epubs.siam.org/doi/abs/10.1137/0211025) requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the [crossing number inequality](https://en.wikipedia.org/wiki/Crossing_number_inequality) suggests that it may not be necessary to have that many crossings.

Is there a way to reduce 3SAT to PLANAR-3SAT in time $O(m^{2-\varepsilon})$ with $\varepsilon>0$ (or less) for subclasses of 3SAT (e.g., read-(at most)-$r$ 3SAT with bounded $r$)?

**Tags:** cc.complexity-theory, graph-theory, reductions, polynomial-time, boolean-formulas

> **Comments:**
> **username_1**: I believe such a reduction would refute ETH, using fast exptime algorithms for planar-3sat. (If we are defining planar-3sat in terms of the "clause-clause" graph.)  
> **username_0**: @RyanWilliams Indeed. I know refuting ETH is a tall order, but the bipartite graphs related to 3SAT have limitations in their degree sequences, especially if appearance of variables is restricted. The crossing number lemma leaves room for subclasses of these graphs to have a crossing number in $o(m^2)$. I now restrict the question to subclasses of 3SAT, as this is slightly more likely.  
> **username_2**: For SAT instances with $O(n)$ clauses the "sufficuently many edges compared to vertices" of the crossing number inequality does not hold. For instances with a superlinear number of clauses, applying the sparsification lemma and then then the standard reduction does the job.  
> **username_0**: @username_2 For 3SAT instances with $n$ variables and $m$ clauses, if we fix $\alpha=m/n=4$, then we have that the number of edges is $e=3m=3 \alpha n = 12n$, which fulfills the requirement $e>4n$ for the crossing number lemma to hold. Am I missing something?  
> **username_2**: The part about the crossing number inequality in my previous comment is nonsense. In fact the crossing number inequality is in the wrong direction to have any bearing on this question - it *lower bounds* the number of crossings, and the bound is not tight for graphs with a linear number of edges. Indeed, 3-regular expanders need $\Omega(n^2)$ crossings.  
> **username_0**: @username_2 Thanks. I found a related question on MO with relevant references that may be helpful to anyone stumbling on this one: https://mathoverflow.net/questions/182404/do-there-exist-sparse-graphs-with-large-crossing-number  

---

## 0 answers

