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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Why do you think something is wrong with it? $\endgroup$
    – Wojowu
    Commented Dec 18, 2019 at 17:16
  • $\begingroup$ @Wojowu I edited, answering your comment. $\endgroup$
    – joro
    Commented Dec 19, 2019 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
    Commented Dec 19, 2019 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
    Commented Dec 19, 2019 at 11:46
  • $\begingroup$ Crossposted to CSE. $\endgroup$
    – joro
    Commented Dec 19, 2019 at 11:48

1 Answer 1

Reset to default
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'$.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 19, 2019 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
    Commented Dec 19, 2019 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .