Straight-line embedding planar graph

1.4k Views Asked by At

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.

2

There are 2 best solutions below

2
On BEST ANSWER

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.

1
On

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