Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Fáry's theorem
Summary
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 , , and .
One way of proving Fáry's theorem is to use mathematical induction. Let G be a simple plane graph with n vertices; we may add edges if necessary so that G is a maximally plane graph. If n < 3, the result is trivial. If n ≥ 3, then all faces of G 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 a, b, c forming a triangular face of G. We prove by induction on n that there exists a straight-line combinatorially isomorphic re-embedding of G in which triangle abc 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 n = 3 and a, b and c are the only vertices in G. Thus, we may assume that n ≥ 4.
By Euler's formula for planar graphs, G has 3n − 6 edges; equivalently, if one defines the deficiency of a vertex v in G to be 6 − deg(v), the sum of the deficiencies is 12. Since G has at least four vertices and all faces of G are triangles, it follows that every vertex in G has degree at least three. Therefore each vertex in G has deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex v with at most five neighbors that is different from a, b and c. Let G' be formed by removing v from G and retriangulating the face f formed by removing v.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.