Fáry's theorem

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Template:Harvs, Template:Harvs, and Template:Harvs.

Proof

Induction step for proof of Fáry's theorem.

One way of proving Fáry's theorem is to use mathematical induction. Let Template:Mvar be a simple plane graph with Template:Mvar vertices; we may add edges if necessary so that Template:Mvar is a maximally plane graph. If Template:Math < 3, the result is trivial. If Template:Math ≥ 3, then all faces of Template:Mvar must be triangles, as we could add an edge into any face with more sides while preserving planarity, contradicting the assumption of maximal planarity. Choose some three vertices Template:Math forming a triangular face of Template:Mvar. We prove by induction on Template:Mvar that there exists a straight-line combinatorially isomorphic re-embedding of Template:Mvar in which triangle Template:Math is the outer face of the embedding. (Combinatorially isomorphic means that the vertices, edges, and faces in the new drawing can be made to correspond to those in the old drawing, such that all incidences between edges, vertices, and faces—not just between vertices and edges—are preserved.) As a base case, the result is trivial when Template:Math and Template:Mvar, Template:Mvar and Template:Mvar are the only vertices in Template:Mvar. Thus, we may assume that Template:Math ≥ 4.

By Euler's formula for planar graphs, Template:Mvar has Template:Math edges; equivalently, if one defines the deficiency of a vertex Template:Mvar in Template:Mvar to be Template:Math, the sum of the deficiencies is Template:Math. Since Template:Mvar has at least four vertices and all faces of Template:Mvar are triangles, it follows that every vertex in Template:Mvar has degree at least three. Therefore each vertex in Template:Mvar has deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex Template:Mvar with at most five neighbors that is different from Template:Mvar, Template:Mvar and Template:Mvar. Let Template:Math be formed by removing Template:Mvar from Template:Mvar and retriangulating the face Template:Mvar formed by removing Template:Mvar. By induction, Template:Mvar has a combinatorially isomorphic straight line re-embedding in which Template:Mvar is the outer face. Because the re-embedding of Template:Mvar was combinatorially isomorphic to Template:Mvar, removing from it the edges which were added to create Template:Mvar leaves the face Template:Mvar, which is now a polygon Template:Mvar with at most five sides. To complete the drawing to a straight-line combinatorially isomorphic re-embedding of Template:Mvar, Template:Mvar should be placed in the polygon and joined by straight lines to the vertices of the polygon. By the art gallery theorem, there exists a point interior to Template:Mvar at which Template:Mvar can be placed so that the edges from Template:Mvar to the vertices of Template:Mvar do not cross any other edges, completing the proof.

The induction step of this proof is illustrated at right. Template:Clear

Related results

De Fraysseix, Pach and Pollack showed how to find in linear time a straight-line drawing in a grid with dimensions linear in the size of the graph, giving a universal point set with quadratic size. A similar method has been followed by Schnyder to prove enhanced bounds and a characterization of planarity based on the incidence partial order. His work stressed the existence of a particular partition of the edges of a maximal planar graph into three trees known as a Schnyder wood.

Tutte's spring theorem states that every 3-connected planar graph can be drawn on a plane without crossings so that its edges are straight line segments and an outside face is a convex polygon (Tutte 1963). It is so called because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

Steinitz's theorem states that every 3-connected planar graph can be represented as the edges of a convex polyhedron in three-dimensional space. A straight-line embedding of $G,$ of the type described by Tutte's theorem, may be formed by projecting such a polyhedral representation onto the plane.

The Circle packing theorem states that every planar graph may be represented as the intersection graph of a collection of non-crossing circles in the plane. Placing each vertex of the graph at the center of the corresponding circle leads to a straight line representation.

Template:Unsolved Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The truth of Harborth's conjecture remains unknown. Integer-distance straight line embeddings are known to exist for cubic graphs.

Template:Harvtxt raised the question of whether every graph with a linkless embedding in three-dimensional Euclidean space has a linkless embedding in which all edges are represented by straight line segments, analogously to Fáry's theorem for two-dimensional embeddings.

See also

• Bend minimization

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.