View source for Fáry's theorem

{{Short description|Planar graphs have straight drawings}}
{{Other uses|Fáry–Milnor theorem}}

In the [[mathematical]] field of [[graph theory]], '''Fáry's theorem''' states that any [[simple graph|simple]], [[planar graph]] can be [[Graph drawing|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 {{harvs|authorlink=Klaus Wagner (mathematician)|first=Klaus|last=Wagner|year=1936|txt}}, {{harvs|authorlink=István Fáry|last=Fáry|year=1948|txt}}, and {{harvs|first=Sherman K.|last=Stein|authorlink= Sherman K. Stein |year=1951|txt}}.

== Proof ==
[[File:Fary-induction.svg|thumb|right|Induction step for proof of Fáry's theorem.]]
One way of proving Fáry's theorem is to use [[mathematical induction]].<ref>The proof that follows can be found in {{citation|title=Graphs & Digraphs|first1=Gary|last1=Chartrand|first2=Linda|last2=Lesniak|first3=Ping|last3=Zhang|author3-link=Ping Zhang (graph theorist)|edition=5th|publisher=CRC Press|year=2010|isbn=9781439826270|pages=259–260|url=https://books.google.com/books?id=K6-FvXRlKsQC&pg=PA259}}.<!-- It's entirely possible that Chartrand et al got the proof from here, since their publication date is later than the date the proof was added here. But it's a valid mathematical proof, so there's no problem with circular reasoning. --></ref> Let  {{mvar|G}}  be a simple [[planar graph|plane graph]] with {{mvar|n}} vertices; we may add edges if necessary so that {{mvar|G}} is a maximally plane graph. If {{math|''n''}} < 3, the result is trivial. If {{math|''n''}} ≥ 3, then all faces of  {{mvar|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 {{math|''a'', ''b'', ''c''}} forming a triangular face of {{mvar|G}}. We prove by induction on {{mvar|n}} that there exists a straight-line combinatorially isomorphic re-embedding of {{mvar|G}} in which triangle {{math|''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 {{math|1=''n'' = 3}} and {{mvar|a}}, {{mvar|b}} and {{mvar|c}} are the only vertices in {{mvar|G}}. Thus, we may assume that {{math|''n''}} ≥ 4.

By [[planar graph|Euler's formula]] for planar graphs, {{mvar|G}} has {{math|3''n'' &minus; 6}} edges; equivalently, if one defines the ''deficiency'' of a vertex {{mvar|v}} in {{mvar|G}} to be {{math|6 &minus; [[Degree (graph theory)|deg]](''v'')}}, the sum of the deficiencies is {{math|12}}. Since {{mvar|G}} has at least four vertices and all faces of {{mvar|G}} are triangles, it follows that every vertex in {{mvar|G}} has degree at least three. Therefore each vertex in {{mvar|G}} has deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex {{mvar|v}} with at most five neighbors that is different from {{mvar|a}}, {{mvar|b}} and {{mvar|c}}. Let {{math|''G'''}} be formed by removing {{mvar|v}} from {{mvar|G}} and retriangulating the face {{mvar|f}} formed by removing {{mvar|v}}.  By induction, {{mvar|G'}} has a combinatorially isomorphic straight line re-embedding in which {{mvar|abc}} is the outer face. Because the re-embedding of {{mvar|G'}} was combinatorially isomorphic to {{mvar|G'}}, removing from it the edges which were added to create {{mvar|G'}} leaves the face {{mvar|f}}, which is now a polygon {{mvar|P}} with at most five sides.  To complete the drawing to a straight-line combinatorially isomorphic re-embedding of {{mvar|G}}, {{mvar|v}} should be placed in the polygon and joined by straight lines to the vertices of the polygon. By the [[Art gallery problem#Chvátal's art gallery theorem|art gallery theorem]], there exists a point interior to {{mvar|P}} at which {{mvar|v}} can be placed so that the edges from {{mvar|v}} to the vertices of {{mvar|P}} do not cross any other edges, completing the proof.

The induction step of this proof is illustrated at right.
{{clear|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, giving a [[universal point set]] with quadratic size. A similar method has been followed by Schnyder to prove enhanced bounds and a [[Schnyder's theorem|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 [[Spring (device)|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 <math>G,</math> 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.

{{unsolved|mathematics|Does every planar graph have a straight line representation in which all edge lengths are integers?}}
[[Heiko Harborth]] raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers.<ref>{{harvtxt|Harborth|Kemnitz|Möller|Süssenbach|1987}}; {{harvtxt|Kemnitz|Harborth|2001}}; {{harvtxt|Mohar|Thomassen|2001}}; {{harvtxt|Mohar|2003}}.</ref> The truth of [[Harborth's conjecture]] remains unknown. Integer-distance straight line embeddings are known to exist for [[cubic graph]]s.<ref>{{harvtxt|Geelen|Guo|McKinnon|2008}}.</ref>

{{harvtxt|Sachs|1983}} 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]]

==Notes==
{{Reflist}}

== References ==
*{{Citation
  | last = Fáry | first = István | authorlink = István Fáry
  | title = On straight-line representation of planar graphs
  | journal = Acta Sci. Math. (Szeged)
  | volume = 11
  | year = 1948
  | pages = 229–233
  | mr = 0026311 }}.
*{{Citation
  | last1 = de Fraysseix | first1 = Hubert
  | last2 = Pach | first2 = János | author2-link = János Pach
  | last3 = Pollack | first3 = Richard
  | chapter = Small sets supporting Fary embeddings of planar graphs
  | title = Twentieth Annual ACM Symposium on Theory of Computing
  | year = 1988
  | pages = 426–433
  | doi = 10.1145/62212.62254
  | isbn = 0-89791-264-0| s2cid = 15230919
 | chapter-url = http://purl.umn.edu/4760
 | doi-access = free
  }}.
*{{Citation
  | last1 = de Fraysseix | first1 = Hubert
  | last2 = Pach | first2 = János | author2-link = János Pach
  | last3 = Pollack | first3 = Richard
  | title = How to draw a planar graph on a grid
  | journal = Combinatorica
  | year = 1990
  | volume = 10
  | pages = 41–51
  | mr = 1075065 
  | doi = 10.1007/BF02122694| s2cid = 6861762
 }}.
*{{Citation
 | last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
 | last2 = Guo | first2 = Anjie
 | last3 = McKinnon | first3 = David
 | doi = 10.1002/jgt.20304
 | issue = 3
 | journal = [[Journal of Graph Theory]]
 | pages = 270–274
 | title = Straight line embeddings of cubic planar graphs with integer edge lengths
 | url = http://www.math.uwaterloo.ca/~dmckinnon/Papers/Planar.pdf
 | volume = 58
 | year = 2008}}.
*{{citation
 | last1 = Harborth | first1 = Heiko
 | last2 = Kemnitz | first2 = Arnfried
 | last3 = Möller | first3 = Meinhard
 | last4 = Süssenbach | first4 = Andreas
 | issue = 5
 | journal = [[Elemente der Mathematik]]
 | mr = 905393
 | pages = 118–122
 | title = Ganzzahlige planare Darstellungen der platonischen Körper
 | url = https://eudml.org/doc/141411
 | volume = 42
 | year = 1987}}.
*{{Citation
 | last1 = Kemnitz | first1 = A.
 | last2 = Harborth | first2 = H.
 | doi = 10.1016/S0012-365X(00)00442-8
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 191–195
 | title = Plane integral drawings of planar graphs
 | volume = 236
 | year = 2001| issue = 1–3
 | doi-access = free
 }}.
*{{Citation
  | last = Mohar | first = Bojan | authorlink = Bojan Mohar
  | year = 2003
  | url = http://www.fmf.uni-lj.si/~mohar/Book/BookProblems.html
  | title = Problems from the book Graphs on Surfaces}}.
*{{Citation
  | last1 = Mohar | first1 = Bojan | author1-link = Bojan Mohar | last2 = Thomassen | first2 = Carsten | author2-link = Carsten Thomassen (mathematician)
  | year = 2001
  | title = Graphs on Surfaces
  | publisher = Johns Hopkins University Press
  | pages = roblem 2.8.15
  | isbn = 0-8018-6689-8}}.
*{{Citation
 | last = Sachs | first = Horst | author-link = Horst Sachs
 | doi = 10.1007/BFb0071633
 | editor1-last = Horowiecki | editor1-first = M.
 | editor2-last = Kennedy | editor2-first = J. W.
 | editor3-last = Sysło | editor3-first = M. M.
 | pages = 230–241
 | publisher = Springer-Verlag
 | series = Lecture Notes in Mathematics
 | title = Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981
 | volume = 1018
 | year = 1983
 | chapter = On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem
 | isbn = 978-3-540-12687-4}}.
* {{Citation
  | last = Schnyder | first = Walter
  | chapter = Embedding planar graphs on the grid
  | chapter-url = http://portal.acm.org/citation.cfm?id=320176.320191
  | title = Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA)
  | year = 1990
  | pages = 138–148| isbn = 9780898712513
 }}.
*{{Citation
  | last = Stein | first = S. K. | authorlink = Sherman K. Stein
  | title = Convex maps
  | journal = [[Proceedings of the American Mathematical Society]]
  | volume = 2
  | year = 1951
  | pages = 464–466
  | mr = 0041425
  | doi = 10.2307/2031777
  | issue = 3
  | jstor = 2031777| doi-access = free
  }}.
*{{Citation
 | last = Tutte | first = W. T. | authorlink = W. T. Tutte
 | title = How to draw a graph
 | journal = Proceedings of the London Mathematical Society
 | volume = 13
 | year = 1963
 | pages = 743–767
 | mr = 0158387 
 | doi = 10.1112/plms/s3-13.1.743}}.
*{{Citation
  | last = Wagner | first = Klaus | authorlink = Klaus Wagner (mathematician)
  | title = Bemerkungen zum Vierfarbenproblem
  | journal = Jahresbericht der Deutschen Mathematiker-Vereinigung
  | volume = 46
  | year = 1936
  | pages = 26–32
  | url = http://www.digizeitschriften.de/index.php?id=resolveppn&PPN=GDZPPN002131633}}.

{{DEFAULTSORT:Fary's Theorem}}
[[Category:Statements about planar graphs]]
[[Category:Articles containing proofs]]
[[Category:Theorems in graph theory]]