5
$\begingroup$

Let $e$ be the number of edges and $v \geq 3$ the number of vertices in a graph $G$. We know that if $G$ is planar, then $e \leq 3v-6$. My question is the opposite. Is there some sort of inequality that guarantees planarity?

For example, I know all trees are planar $e = v-1$. So, we could say: If $G$ is a connected graph with $e \leq v-1$, then $G$ is planar.

But, are there better known bounds that guarantee planarity? Also, I'm curious about the same question for outerplanar graphs. Again, in that case, we have an inequality that can determine when a graph is not outerplanar, but I wonder if there is one that could guarantee that a graph is outerplanar.

Assume connectedness if necessary.

$\endgroup$
  • $\begingroup$ If $G$ is not connected, the only inequalities that guarantee planarity are $e\le8$ and $v\le4$. Either one will do. $\endgroup$ – Gerry Myerson Oct 13 '12 at 12:12
2
$\begingroup$

By Kuratowsky's Theorem a graph is planar if it does not contain a subdivision of the $K_5$ and $K_{3,3}$ as subgraph.

You require that your graph $G$ is connected, this already needs $v-1$ edges for the spanning tree of $G$. You need at least four edges to make a $K_{3,3}$ out of a spanning tree, so you are safe if you only add 3 more edges. (The $K_5$ is worse in this sense.)

Thus your connected graph is planar, if it has $v+2$ edges. Otherwise, the $K_{3,3}$ has $v=6$ vertices, and $v+3=9$ edges and is not planar.

from a spanning tree to K_3,3 and K_5

$\endgroup$
0
$\begingroup$

If it is connected, $e <= v + 2$ will do. More than that, can't say. Also, make sure of the special cases mentioned above do not get in the way of the above equation.

Salahuddin

http://maths-on-line.blogspot.in/

$\endgroup$

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.