# Reduction SAT to a problem on a planar graph with as few vertices as possible

Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.

I am looking for a reduction is $\phi$ satisfiable to a problem on a planar graph $G$ with as few vertices as possible.

The majority of reductions I have seen use "crossing gadget", which replaces edge crossing by a planar graph.

So far the best reference is $|V(G)|=m^2$.

The motivation is that the treewidth of planar graphs is at most $4.9 \sqrt{|V(G)|}$ and this gives subexponential complexity for problems exponential in the treewidth like Independent Set.

You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time Hypothesis (ETH) is false. This is well-appreciated, yet it has not led to any improvements on running times for CNF-SAT (as far as I know). For more on how ETH has been used to classify the difficulty of planar (and non-planar) graph problems, see e.g. this survey of Lokshtanov, Marx, and Saurabh.
As for reducing the constant in such reductions, achieving $|V(G)| = c m^2$ for $c$ as small as possible, I don't know how much effort has been devoted to this.
• I don't know exactly which problem you mean, but e.g. for 2-CSPs with planar underlying graph on $n$ vertices, $2^{O(\sqrt{n})}$ runtime is possible by known techniques (that you mention) and $2^{o(\sqrt{n})}$ would falsify ETH. – Andy Drucker Mar 21 '15 at 19:13