Fáry's theorem

Fáry's theorem

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 same theorem was proven independently by Wagner, Fáry, and Stein. 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 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.

Proof

Let G be a simple planar graph with n vertices; we may add edges if necessary so that G is maximal planar. All faces of G 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 a,b,c forming a triangular face of G. We prove by induction on n that there exists a straight-line embedding of G in which triangle abc is the outer face of the embedding. As a base case, the result is trivial when n=3 and a, b, and c are the only vertices in G. Otherwise, all vertices in G have at least three neighbors.

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 six minus the degree of v, the sum of the deficiencies is twelve. Each vertex in G can have 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 formed by removing v. By induction, G' has a straight line embedding in which abc is the outer face. Remove the added edges in G', forming a polygon P with at most five sides into which v should be placed to complete the drawing. By the Art gallery theorem, there exists a point interior to P at which v can be placed so that the edges from v to the vertices of P do not cross any other edges, completing the proof.

The induction step of this proof is illustrated at right.

Related results

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.

H. Harborth (Mohar and Thomassen 2001; Mohar 2003) raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The answer remains unknown as of 2006.

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
id = MathSciNet | id = 0026311

* cite conference
author = de Fraysseix, Hubert, Pach, János, and Pollack, Richard
title = Small sets supporting Fary embeddings of planar graphs
booktitle = Twentieth Annual ACM Symposium on Theory of Computing
year = 1988
pages = 426–433
doi = 10.1145/62212.62254

* cite journal
author = de Fraysseix, Hubert, Pach, János, and Pollack, Richard
title = How to draw a planar graph on a grid
journal = Combinatorica
year = 1990
volume = 10
pages = 41–51
id = MathSciNet | id = 1075065
doi = 10.1007/BF02122694

* cite web
author = Mohar, 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

* cite book
author = Mohar, Bojan; Thomassen, Carsten
year = 2001
title = Graphs on Surfaces
publisher = Johns Hopkins University Press
pages = problem 2.8.15
id = ISBN 0801866898

* cite conference
author = Schnyder, Walter
title = Embedding planar graphs on the grid
url = http://portal.acm.org/citation.cfm?id=320176.320191
booktitle = Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA)
year = 1990
pages = 138–148

*cite journal
author = Stein, S. K.
title = Convex maps
journal = Proceedings of the American Mathematical Society
volume = 2
year = 1951
pages = 464–466
id = MathSciNet | id = 0041425
doi = 10.2307/2031777

*cite journal
author = Tutte, W. T.
title = How to draw a graph
journal = Proceedings of the London Mathematical Society
volume = 13
year = 1963
pages = 743–767
id = MathSciNet | id = 0158387
doi = 10.1112/plms/s3-13.1.743

*cite journal
author = Wagner, Klaus
title = Bemerkungen zum Vierfarbenproblem
journal = Jahresbericht. German. Math.-Verein.
volume = 46
year = 1936
pages = 26–32


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Fary-Milnor theorem — In mathematics, the Fary Milnor theorem in knot theory states that for any knot K in R3, if the total curvature :oint K kappa ,ds leq 4pi then K is an unknot, where kappa is the curvature (it is possible for an unknotted curve to have large total …   Wikipedia

  • Fary — may refer to one of the following:*El Fary, a Spanish singer and actor. *István Fáry, a Hungarian mathematician, the namesake of the Fáry s theorem *John G. Fary, a U.S. Representative from Illinois. *Fary Faye, a football forward from Senegal …   Wikipedia

  • Théorème de Fary-Milnor —  Ne doit pas être confondu avec le théorème de Fáry (en) sur les graphes planaires. En théorie des nœuds, le théorème de Fary Milnor dit qu en dimension 3, une courbe fermée simple lisse dont la courbure totale est as …   Wikipédia en Français

  • István Fáry — Infobox Scientist name = István Fáry image width = caption = birth date = birth date|1922|6|30|mf=y birth place = Gyula, Hungary death date = Death date|1984|11|2|mf=y death place = El Cerrito, California residence = United States nationality =… …   Wikipedia

  • Circle packing theorem — Example of the circle packing theorem on K5, the complete graph on five vertices, minus one edge. The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • John Milnor — For those of a similar name, see John Milner (disambiguation). John Willard Milnor Born February 20, 1931 ( …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • John Milnor — John Willard Milnor John Willard Milnor (* 20. Februar 1931 in Orange (New Jersey)) ist ein US amerikanischer Mathematiker, dem 1962 für besondere Verdienste in der Mathematik die Fields Medaille verliehen wurde. Zur Zeit ist er an der State… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”