Addding edges to spanning tree without destroying planarity

Question

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$

Answer 1

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