Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Wagner's_theorem> ?p ?o. }
Showing items 1 to 16 of
16
with 100 items per page.
- Wagner's_theorem abstract "In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K5 minor. That is, by assuming a higher level of connectivity, the other graph K3,3 can be made unnecessary in the characterization. Using this fact, it is possible to decompose the graphs that do not have a K5 minor into combinations of planar graphs and the eight-vertex Wagner graph, glued together by clique-sum operations.Wagner published both theorems in 1937, subsequent to the 1930 publication of Kuratowski's theorem, according to which a graph is planar if and only if it does not contain as a subgraph a subdivision of one of the same two forbidden graphs K5 and K3,3. In a sense, Kuratowski's theorem is stronger than Wagner's theorem: a subdivision can be converted into a minor of the same type by contracting all but one edge in each path formed by the subdivision process, but converting a minor into a subdivision of the same type is not always possible. However, in the case of the two graphs K5 and K3,3, it is straightforward to prove that a graph that has at least one of these two graphs as a minor also has at least one of them as a subdivision, so the two theorems are equivalent.Wagner's theorem is an important precursor to the theory of graph minors, which culminated in the proofs of two deep and far-reaching results: the graph structure theorem (a generalization of Wagner's clique-sum decomposition of K5-minor-free graphs) and the Robertson–Seymour theorem (a generalization of the forbidden minor characterization of planar graphs, stating that every graph family closed under the operation of taking minors has a characterization by a finite number of forbidden minors). Analogues of Wagner's theorem can also be extended to the theory of matroids: in particular, the same two graphs K5 and K3,3 (along with three other forbidden configurations) appear in a characterization of the graphic matroids by forbidden matroid minors.".
- Wagner's_theorem thumbnail Petersen_Wagner_minors.svg?width=300.
- Wagner's_theorem wikiPageID "3126130".
- Wagner's_theorem wikiPageRevisionID "538010883".
- Wagner's_theorem hasPhotoCollection Wagner's_theorem.
- Wagner's_theorem subject Category:Graph_minor_theory.
- Wagner's_theorem subject Category:Planar_graphs.
- Wagner's_theorem subject Category:Theorems_in_graph_theory.
- Wagner's_theorem comment "In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K5 minor.".
- Wagner's_theorem label "Wagner's theorem".
- Wagner's_theorem sameAs m.0pl1ytk.
- Wagner's_theorem sameAs Q7959587.
- Wagner's_theorem sameAs Q7959587.
- Wagner's_theorem wasDerivedFrom Wagner's_theorem?oldid=538010883.
- Wagner's_theorem depiction Petersen_Wagner_minors.svg.
- Wagner's_theorem isPrimaryTopicOf Wagner's_theorem.
