Straight-line embedding planar graph

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.

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.

• 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? Oct 22 '13 at 15:46
• 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.) Oct 22 '13 at 21:31

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

• 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? Oct 17 '13 at 1:06