<p>The diameter of <span class="math-container">$G'$</span> will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge <span class="math-container">$O(n)$</span> times, so the diameter can blow up by a factor of <span class="math-container">$O(n)$</span>.</p>

CC BY-SA 4.0
2019-12-19T11:47:09.333Z
2019-12-19T11:47:09.333Z
Laakeri
<p>We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.</p>

<p>Let <span class="math-container">$H$</span>, the planarizing gadget, be planar graph with four
distinguished vertices <span class="math-container">$u,u',v,v'$</span> on the outer faces.</p>

<p>Take graph <span class="math-container">$G$</span> drawn on the plane. Add new vertex <span class="math-container">$S$</span>,
adjacent to all vertices of <span class="math-container">$G$</span>. So far the diameter is
at most two.</p>

<p>Replace each pair of crossing edges <span class="math-container">$(u,u'),(v,v')$</span> by
new copy of the gadget <span class="math-container">$H$</span>.</p>

<p>The resulting graph <span class="math-container">$G'$</span> is planar with diameter <span class="math-container">$D = 2\max(d(u,u'),d(v,v'))$</span>
where <span class="math-container">$d$</span> is the distance in <span class="math-container">$H$</span>.</p>

<p>The treewidth of <span class="math-container">$G'$</span> is <span class="math-container">$O(D)$</span>, which is constant for fixed <span class="math-container">$H$</span>,
for reference see <a href="https://cstheory.stackexchange.com/questions/17983/k-outerplanar-graphs-are-subgraphs-of-bounded-diameter-planar-graphs-of-bounded">here</a>.</p>

<p>Similar reduction with specially chosen <span class="math-container">$H$</span> is used to show
NP-hardness of problems for planar graphs.</p>

<blockquote>
  <p>What is wrong with this reduction?</p>
</blockquote>

<p>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 <span class="math-container">$H$</span> might give relation between invariants
of <span class="math-container">$G$</span> and <span class="math-container">$G'$</span>, implying <span class="math-container">$P=NP$</span>.</p>

<p>Another <a href="https://cstheory.stackexchange.com/questions/3758/do-outer-bounded-genus-graphs-have-constant-treewidth">reference</a> claims
"bounded genus graphs of bounded diameter have bounded treewidth".</p>

CC BY-SA 4.0
2019-12-19T11:47:02.957Z
Crossposted to MO https://mathoverflow.net/questions/348646/reduction-graph-to-planar-bounded-treewidth-graph
joro
<graph-theory><graph-algorithms><planar-graphs>
Reduction graph to planar bounded treewidth and bounded diameter graph
joro
# Reduction graph to planar bounded treewidth and bounded diameter graph

(Asked by: username_0 on 2019-12-19)

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](https://cstheory.stackexchange.com/questions/17983/k-outerplanar-graphs-are-subgraphs-of-bounded-diameter-planar-graphs-of-bounded).

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](https://cstheory.stackexchange.com/questions/3758/do-outer-bounded-genus-graphs-have-constant-treewidth) claims
"bounded genus graphs of bounded diameter have bounded treewidth".

**Tags:** graph-theory, graph-algorithms, planar-graphs
> **Comments:**
> **username_0**: Crossposted to MO https://mathoverflow.net/questions/348646/reduction-graph-to-planar-bounded-treewidth-graph  

---

## 1 answers

### Answer by username_1 on 2019-12-19. Score: 3 | Accepted answer

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


---

