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$


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.

| cite | improve this answer | |

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.