Lesson 5

Theorem (Wagner, Fáry). Any planar graph admits an embedding in which each edge is a straight-line segment.

Proof. We will prove by induction on the number of vertices a stronger statement: any proper embedding of a graph can be continuously transformed into a proper embedding in which all edges are straight-line segments.

For three vertices the statement holds, so we assume the graph has at least four vertices. We assume the graph is a maximal planar graph, meaning no edge can be added without losing planarity. This, in particular, means that all its faces (including the outer one) are triangles.

We will show that in our (maximal planar) graph there are at least four vertices of degree at most five. Each face of our graph is a triangle and each edge belongs to two faces, so \(|F|=\frac{2|E|}{3}\). Then, by Euler’s formula, \(|E|=3|V|-6\). Define the deficit of a vertex: \(d(v)=6-\deg(v)\). The sum of all deficits is 12: \[\sum_{v \in V}(6-\deg(v))=6|V|-2|E|=6|V|-2(3|V|-6)=12 \ .\] On the other hand, the degree of each vertex is at least three, so the deficit of each vertex is at most three. Thus, for the total deficit to be twelve, there must be at least four vertices with positive deficit.

Now consider an arbitrary embedding of graph \(G\). Its outer face is a triangle, so there exists a vertex \(v\) of degree \(k \le 5\) not lying on the outer face. If we remove vertex \(v\) from the graph, a face with \(k\) edges is formed. Now straighten the resulting graph. The considered face becomes a \(k\)-gon (possibly non-convex). By the Art Gallery Theorem, there exists a point inside this \(k\)-gon from which segments to all its vertices do not cross its sides.◼