# Reduction graph to planar bounded treewidth and bounded diameter 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$$, for reference see here.

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$$.

Another reference claims "bounded genus graphs of bounded diameter have bounded treewidth".

The diameter of $$G'$$ will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge $$O(n)$$ times, so the diameter can blow up by a factor of $$O(n)$$.