# Reduction graph to planar bounded treewidth graph

We got reduction graph to planar bounded treewidth graph, but this is unlikely to be true.

Let $$H$$, the planarizing gadget, be planar graph with four distinguished vertices $$u,u',v,v'$$ on the outer faces.

Take graph $$G$$ drawn on the plane. Add new vertex $$S$$, adjacent to all vertices of $$G$$. So far the diameter is at most two.

Replace each pair of crossing edges $$(u,u'),(v,v')$$ by new copy of the gadget $$H$$.

The resulting graph $$G'$$ is planar with diameter $$D = 2\max(d(u,u'),d(v,v'))$$ where $$d$$ is the distance in $$H$$.

The treewidth of $$G'$$ is $$O(D)$$, which is constant for fixed $$H$$.

Similar reduction with specially chosen $$H$$ is used to show NP-hardness of problems for planar graphs.

What is wrong with this reduction?

Correctness of the reduction is unlikely, because for bounded treewidth graphs a lot of graph invariants are computable in polynomial time and choosing suitable gadget $$H$$ might give relation between invariants of $$G$$ and $$G'$$, implying $$P=NP$$.

We cannot use it directly as gadget $$H$$ since the $$S$$ vertex increases the chromatic number, but there is potential approach to use it and then subdivide all edges $$(S,t)$$ twice, having the property that $$S$$ can be any color in a valid 3-coloring by adjusting the colors of the degree 2 vertices in the subdivision.

• Why do you think something is wrong with it? Dec 18, 2019 at 17:16
– joro
Dec 19, 2019 at 9:37
• The key word is "might". The main issue to me would seem to be the fact that you have to relate priperties of $G$ to $G'$, which in general would be non-trivial. At any rate, even then I don't see how this could be a problem with the construction itself. Dec 19, 2019 at 10:08
• @Wojowu Thanks. I edited with link to 3-coloring planarizing gadget, there is some hope it can work despite the S vertex.
– joro
Dec 19, 2019 at 11:46
• Crossposted to CSE.
– joro
Dec 19, 2019 at 11:48

If gadgets are applied around crossing points then two vertices at distance $$d$$ in $$G$$ are not necessarily at distance $$O(d)$$ in $$G'$$, as a path of length $$d$$ in $$G$$ corresponds to paths of length $$O(d) + O(\text{number of crossings})$$ in $$G'$$.
• That would seem to depend on whether the edges from $S$ can reach every vertex with few crossings. I expect that's not going to be possible for arbitrary $G$. Dec 19, 2019 at 16:27