0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.