High Quality Content by WIKIPEDIA articles! In mathematics, Fary'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 Istvan Fary, although it was proved independently by Klaus Wagner (1936), Fary (1948), and S. K. Stein (1951).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.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.