6
$\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$
1
  • $\begingroup$ If $G$ is not connected, the only inequalities that guarantee planarity are $e\le8$ and $v\le4$. Either one will do. $\endgroup$ Oct 13, 2012 at 12:12

2 Answers 2

4
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .