Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Steinitz's theorem
Résumé
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. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
This result provides a classification theorem for the three-dimensional convex polyhedra, something that is not known in higher dimensions. It provides a complete and purely combinatorial description of the graphs of these polyhedra, allowing other results on them, such as Eberhard's theorem on the realization of polyhedra with given types of faces, to be proven more easily, without reference to the geometry of these shapes. Additionally, it has been applied in graph drawing, as a way to construct three-dimensional visualizations of abstract graphs. Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."
The theorem appears in a 1922 publication of Ernst Steinitz, after whom it is named. It can be proven by mathematical induction (as Steinitz did), by finding the minimum-energy state of a two-dimensional spring system and lifting the result into three dimensions, or by using the circle packing theorem.
Several extensions of the theorem are known, in which the polyhedron that realizes a given graph has additional constraints; for instance, every polyhedral graph is the graph of a convex polyhedron with integer coordinates, or the graph of a convex polyhedron all of whose edges are tangent to a common midsphere.
An undirected graph is a system of vertices and edges, each edge connecting two of the vertices. As is common in graph theory, for the purposes of Steinitz's theorem these graphs are restricted to being finite (the vertices and edges are finite sets) and simple (no two edges connect the same two vertices, and no edge connects a vertex to itself).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.