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$

2 Answers 2

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$
2
  • $\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
    Commented Oct 22, 2013 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
    Commented Oct 22, 2013 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$
1
  • $\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
    Commented Oct 17, 2013 at 1:06

You must log in to answer this question.

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