<p>Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes have the same sign have length approximately $\sqrt n$ (according to the <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem">Erdős–Szekeres theorem</a>).  Add to $G$ one edge for each point $(x_i,y_i)$ in $S$, whose endpoints are the vertices at positions $x_i$ and $n+y_i$ in the path.</p>

<p>Now consider any planar graph sandwiched between $T$ and $G$, and draw it in the plane such that $T$ lies along a horizontal line (possibly causing the other edges to curve rather than being straight, but without crossings). We can partition the edges added to $T$ into four classes: the ones that stay below the line, the ones that stay above the line, the ones that wrap around the left endpoint of $T$, and the ones that wrap around the right endpoint of $T$ (wrapping around exactly two endpoints of $T$ doesn't help — all such edges can be deformed topologically so that they stay above or below the line — and wrapping around more than twice is not possible). In each of these four classes, a subset of non-crossing edges must correspond to a monotonic polygonal chain in $S$. Therefore, the total number of added edges is at most $4\sqrt n + O(1)$.</p>

<p>The Erdős–Szekeres theorem can be used in the other direction to find large subsets of edges that don't cross each other when $T$ is a path. I'm not entirely sure what happens when $T$ isn't a path, but it seems likely to me that the size of the planar subsets you can find only goes up in this case, so that (in the case of a linear number of edges and bounded vertex degree) $\Theta(\sqrt n)$ is the right bound on the number of added edges you can always find.</p>

CC BY-SA 3.0
2015-01-12T21:48:55.170Z
2015-01-12T21:48:55.170Z
David Eppstein
<p>Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ so that $T \cup E_c$ is a planar graph. Is there any known upper or lower bound on the size of $E_c$ in term of $n, m$ and $\Delta$</p>

<graph-theory><co.combinatorics><planar-graphs><topological-graph-theory>
Addding edges to spanning tree without destroying planarity
Hung Le
# Addding edges to spanning tree without destroying planarity

(Asked by: username_0 on 2015-01-12)

Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E\_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ so that $T \cup E\_c$ is a planar graph. Is there any known upper or lower bound on the size of $E\_c$ in term of $n, m$ and $\Delta$

**Tags:** graph-theory, co.combinatorics, planar-graphs, topological-graph-theory

---

## 1 answers

### Answer by username_1 on 2015-01-12. Score: 9 | Accepted answer

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x\_i,y\_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes have the same sign have length approximately $\sqrt n$ (according to the [Erdős–Szekeres theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem)). Add to $G$ one edge for each point $(x\_i,y\_i)$ in $S$, whose endpoints are the vertices at positions $x\_i$ and $n+y\_i$ in the path.

Now consider any planar graph sandwiched between $T$ and $G$, and draw it in the plane such that $T$ lies along a horizontal line (possibly causing the other edges to curve rather than being straight, but without crossings). We can partition the edges added to $T$ into four classes: the ones that stay below the line, the ones that stay above the line, the ones that wrap around the left endpoint of $T$, and the ones that wrap around the right endpoint of $T$ (wrapping around exactly two endpoints of $T$ doesn't help — all such edges can be deformed topologically so that they stay above or below the line — and wrapping around more than twice is not possible). In each of these four classes, a subset of non-crossing edges must correspond to a monotonic polygonal chain in $S$. Therefore, the total number of added edges is at most $4\sqrt n + O(1)$.

The Erdős–Szekeres theorem can be used in the other direction to find large subsets of edges that don't cross each other when $T$ is a path. I'm not entirely sure what happens when $T$ isn't a path, but it seems likely to me that the size of the planar subsets you can find only goes up in this case, so that (in the case of a linear number of edges and bounded vertex degree) $\Theta(\sqrt n)$ is the right bound on the number of added edges you can always find.


---

