Fáry's theorem
Encyclopedia
In mathematics, Fáry's theorem states that any simple planar graph
can be drawn
without crossings so that its edges are straight line segment
s. 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 , , and .
Let 
be a simple planar graph
with
vertices; we may add edges if necessary so that 
is maximal planar. All faces of 
will 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 
forming a triangular face of 
We prove by induction
on
that there exists a straight-line embedding of 
in which triangle 
is the outer face of the embedding. As a base case, the result is trivial when 
and 
and 
are the only vertices in 
Otherwise, all vertices in 
have at least three neighbors.
By Euler's formula
for planar graphs,
has 
edges; equivalently, if one defines the deficiency of a vertex 
in 
to be six minus the degree of 
the sum of the deficiencies is twelve. Each vertex in 
can have deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex 
with at most five neighbors that is different from 
and 
Let 
be formed by removing 
from 
and retriangulating the face formed by removing 
By induction, 
has a straight line embedding in which abc is the outer face. Remove the added edges in 
, forming a polygon 
with at most five sides into which 
should be placed to complete the drawing. By the Art gallery theorem, there exists a point interior to 
at which 
can be placed so that the edges from 
to the vertices of 
do not cross any other edges, completing the proof.
The induction step of this proof is illustrated at right.
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
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.
Heiko Harborth
raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The answer remains unknown . However, integer-distance straight line embeddings are known to exist for cubic graph
s.
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.
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
can be drawn
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
without crossings so that its edges are straight line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s. 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
István Fáry
István Fáry was a Hungarian-born mathematician known for his work in geometry and algebraic topology. He proved Fáry's theorem that every planar graph has a straight line embedding in 1948, and the Fary–Milnor theorem lower-bounding the curvature of a nontrivial knot in 1949.-Biography:Fáry was...
, although it was proved independently by , , and .
Proof
be a simple planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
with
vertices; we may add edges if necessary so that is maximal planar. All faces of will 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 forming a triangular face of We prove by inductionMathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
on
that there exists a straight-line embedding of in which triangle is the outer face of the embedding. As a base case, the result is trivial when and and are the only vertices in Otherwise, all vertices in have at least three neighbors.By Euler's formula
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
for planar graphs,
has edges; equivalently, if one defines the deficiency of a vertex in to be six minus the degree of the sum of the deficiencies is twelve. Each vertex in can have deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex with at most five neighbors that is different from and Let be formed by removing from and retriangulating the face formed by removing By induction, has a straight line embedding in which abc is the outer face. Remove the added edges in , forming a polygon with at most five sides into which should be placed to complete the drawing. By the Art gallery theorem, there exists a point interior to at which can be placed so that the edges from to the vertices of do not cross any other edges, completing the proof.The induction step of this proof is illustrated at right.
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. A similar method has been followed by Schnyder to prove enhanced bounds and a characterization of planaritySchnyder's theorem
In graph theory, Schnyder's theorem is a characterization of planar graphs in termsof the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989....
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
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
.
Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
's spring
Spring (device)
A spring is an elastic object used to store mechanical energy. Springs are usually made out of spring steel. Small springs can be wound from pre-hardened stock, while larger ones are made from annealed steel and hardened after fabrication...
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
Steinitz's theorem
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
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
of the type described by Tutte's theorem, may be formed by projecting such a polyhedral representation onto the plane.The Circle packing theorem
Circle packing theorem
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...
states that every planar graph may be represented as the intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
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.
Heiko Harborth
Heiko Harborth
Heiko Harborth is Professor of Mathematics at Braunschweig University of Technology, 1975–present, and author of more than 188 mathematical publications...
raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The answer remains unknown . However, integer-distance straight line embeddings are known to exist for cubic graph
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
s.
raised the question of whether every graph with a linkless embedding
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...
in three-dimensional Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
has a linkless embedding in which all edges are represented by straight line segments, analogously to Fáry's theorem for two-dimensional embeddings.