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

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

Added Example of 3-Coloring planarizing gadget is in this lecture p.1.

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.

$\endgroup$
  • $\begingroup$ Why do you think something is wrong with it? $\endgroup$ – Wojowu Dec 18 '19 at 17:16
  • $\begingroup$ @Wojowu I edited, answering your comment. $\endgroup$ – joro Dec 19 '19 at 9:37
  • $\begingroup$ 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. $\endgroup$ – Wojowu Dec 19 '19 at 10:08
  • $\begingroup$ @Wojowu Thanks. I edited with link to 3-coloring planarizing gadget, there is some hope it can work despite the S vertex. $\endgroup$ – joro Dec 19 '19 at 11:46
  • $\begingroup$ Crossposted to CSE. $\endgroup$ – joro Dec 19 '19 at 11:48
2
$\begingroup$

If gadgets are applied to pairs of crossing edges as described then I'm not sure such gadgets exist as they probably preserve the presence of forbidden minors.

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Gadgets are at crossing edges and indeed the diameter is large. Will the diameter still be large if I require G to be planar? Then all vertices will be at constant distance from S? $\endgroup$ – joro Dec 19 '19 at 16:24
  • $\begingroup$ 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$. $\endgroup$ – Ben Barber Dec 19 '19 at 16:27

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.