5
$\begingroup$

I want to prove that every normal planar graph has a straight-line embedding.

First, I assume that the planar graph $G$ is maximal planar, i.e the number of edges is $3n-6$ for $|G|=|V(G)|\ge3$. If the graph is not maximal planar I simply add some edges until it is maximal. I also know that all faces form triangles.

Now I want to prove the result with induction with respect to $n$.

$n=3:$ This case is trivial, it is just a triangle.

$n-1\rightarrow n$. I assume I know that the embedding works for a graph with $n-1$ vertices. I do not know hot to conclude. Intuitively it is clear to me because it is nothing more than some triangles which I clue together.

Maybe you can help me.

$\endgroup$
6
+50
$\begingroup$

Note that all faces of maximal planar graph (including the outer one) are triangles.

Consider a maximal planar graph $G$ on $n$ vertices. It has vertex $v$ such that $\deg v \le 5$ (otherwise it woudl have at least $\frac{6n}2 = 3n > 3n - 6$ edges). Since all faces of $G$ are triangles, there is also cycle $C$ such that $V(C) = N(v)$. Let remove $v$ from $G$, add $|C| - 3$ chords into $C$ (if $|C| = 5$ chords should be adjacent) and get maximal planar graph $H$ on $n - 1$ vertices. By induction hypothesis it has a straight-line embedding. Now remove all edges from $E(H) \setminus E(G)$. If cycle $C$ is an inner face (of size at most 5) it is always possible to place $v$ inside this face and connect to its neigbours in $G$ by straight lines. If $C$ is the outer face then all (at most 2) edges from $E(H) \setminus E(G)$ are edges of outer face of embedding of $H$. Then it is possible to place $v$ on outer face of $H - (E(H) \setminus E(G))$ and connect it to all neighbours in $G$ by straight lines.

P. S. Both cases of placing $v$ are obvious when $\deg v = 3$ and $\deg v = 4$, and not hard to proove for $\deg v = 5$; ask in comments if needed.

$\endgroup$
  • $\begingroup$ I do not understand the part with the chords quite well. Consider foor exmaple the case n=4, so the graph has 4 vertices. The picture is on mathworld.wolfram.com/TriangulatedGraph.html Now lets say you remove the vertex which is directly in the center, where can you draw two adjacent chords? $\endgroup$ – Alexander Oct 22 '13 at 15:46
  • $\begingroup$ I'm sorry, cases $\deg v = 3$ and $\deg v = 4$ were obvious for me, so I was thinking about case $\deg v = 5$. So I meant that for $|C| = 5$ we add two adjacent chords, for $|C| = 4$ only one chord, and for $|C| = 3$ don't add anything. (Edited the answer.) $\endgroup$ – Smylic Oct 22 '13 at 21:31
2
$\begingroup$

This result is known as Fáry's theorem, see e.g., http://en.wikipedia.org/wiki/Fary%27s_theorem

There are other proofs; for example it follows from the main theorem in Tutte's paper "How to draw a graph".

$\endgroup$
  • $\begingroup$ I have already seen the wikipedia article but they introduce "deficiencies" and I would prefer avoiding them. Is there any way to complete my induction approach? $\endgroup$ – Alexander Oct 17 '13 at 1:06

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.