Topological graph theory

The topological graph theory is a branch of mathematics , which is located at the interface between graph theory and topology and is influenced by related areas such as geometric graph theory , geometry , knot theory and group theory . It deals with problems related to the representation of graphs in topological spaces . The development of topological graph theory was largely determined and driven by the four-color problem .

Concept of representation

definition

A representation of a given graph is understood to be a graph isomorphism from this to a graph for which the following conditions are met: ${\displaystyle G}$ ${\displaystyle G^{'}}$

1. The union of the set of nodes and edges of is contained as a subspace in a topological space . ${\displaystyle G^{'}}$ ${\displaystyle X^{'}}$
2. Each edge of is a Jordan curve in  . ${\displaystyle G^{'}}$ ${\displaystyle X^{'}}$
3. In an nodes and an edge if and only incident when in the on associated point start or end point to be associated Jordan curve is. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle G^{'}}$ ${\displaystyle v}$ ${\displaystyle v^{'}}$ ${\displaystyle e}$ ${\displaystyle e^{'}}$
4. In two nodes and if and adjazent when those which -Jordankurven and connect with each other, with the exact and incident belong edges. ${\displaystyle G}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle G^{'}}$ ${\displaystyle {v_{1}}^{'}}$ ${\displaystyle {v_{2}}^{'}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle G}$

Names and ways of speaking

• A graph of the type mentioned is called a topological graph . ${\displaystyle G^{'}}$
• If there is a graph isomorphism as above, one speaks of an embedding of the graph in the topological space ${\displaystyle G}$ ${\displaystyle X^{'}}$ .
• In short, one speaks in relation to the representation of the graph and then also says that the given graph realizes or represents (or similar). ${\displaystyle G^{'}}$ ${\displaystyle G}$ ${\displaystyle G^{'}}$ ${\displaystyle G}$
• The above-mentioned subspace is usually also referred to as . ${\displaystyle G^{'}}$
• If and are all edges of lines that do not intersect at all or at most in a single point of , this is called a straight line representation of . Such a straight line representation is also referred to as a route graph . ${\displaystyle G^{'}\subset \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 1)}$ ${\displaystyle G^{'}}$ ${\displaystyle G^{'}}$ ${\displaystyle G^{'}}$ ${\displaystyle G}$

Topological graph theory in the narrower sense

In the narrower sense and mainly the investigations of the topological graph theory take place in the following starting situation:

1. ${\displaystyle G}$is a finite simple graph .
2. The topological space is a surface in the d- dimensional Euclidean space . This is usually the case. ${\displaystyle X^{'}}$ ${\displaystyle \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)}$ ${\displaystyle \mathbb {R} ^{d}\;(d=2,3,4)}$
3. The edges of the display are simple Jordan curves in . ${\displaystyle G^{'}}$ ${\displaystyle X^{'}}$
4. ${\displaystyle G^{'}}$is a path-connected space .
5. The node set of has exactly the start and end point in common with every single edge of . ${\displaystyle G^{'}}$ ${\displaystyle G^{'}}$
6. Two different edges of either do not intersect at all or at most in a single node of . ${\displaystyle G^{'}}$ ${\displaystyle G^{'}}$
7. The corresponding topological map has only a finite number of countries, of which either none or only one is unlimited . ${\displaystyle G^{'}}$

If under the conditions mentioned there is even a plane graph , then  one speaks of a plane representation . ${\displaystyle G^{'}}$ ${\displaystyle G^{'}\subset X^{'}=\mathbb {R} ^{2}}$

Central questions of topological graph theory

In topological graph theory, the following questions are addressed:

• In which topological spaces can a given graph be embedded and what are its features? ${\displaystyle X^{'}}$ ${\displaystyle G}$
  • Specifically: In which areas can a given graph be embedded and what are its characteristics (e.g. gender , orientation )? ${\displaystyle F^{'}\subseteq \mathbb {R} ^{d}}$
    • Question of flattenability : For which graphs can a plane representation be found and how can they be described - for example in a combinatorial or group -theoretric way? ${\displaystyle G}$ ${\displaystyle G^{'}}$
• In which Euclidean space is a given graph can with linear representation embed? ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle G}$ ${\displaystyle G^{'}\subset \mathbb {R} ^{d}}$
  • Special: Which graphs have a linear representation as -dimensional Polytopgraph , so that with just one route graph realize whose nodes and edges accurately from the corners and edges of a convex polytope in the stand? ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle G^{'}}$ ${\displaystyle \mathbb {R} ^{d}}$
    • Special: Which graphs have a linear representation as -dimensional Polyedergraph , so that with just one route graph realize whose nodes and edges accurately from the corners and edges of a convex polyhedron in the stand? ${\displaystyle G}$ ${\displaystyle 3}$ ${\displaystyle G^{'}}$ ${\displaystyle \mathbb {R} ^{3}}$

Significant theorems of topological graph theory

The Topological graph theory includes a wealth of important sentences, of which the first Euler Polyedersatz which Kuratowski's theorem and the four color theorem and its related him significant sentences about Topological maps can be mentioned. Three other classical theorems of topological graph theory deserve special mention , namely Steinitz's fundamental theorem of convex types , Grötzsch's three-color theorem and Tuttesche's theorem on the Hamilton circle problem .

The theorem of Wagner and Fáry can also be related to the four-color theorem , which is fundamental for its proof, since it is only through it that the straight-line representation of a flat graph is ensured. Another sentence is worth mentioning in the same context, which addresses the corresponding question of spatial linear representation in relation to all finite, simple graphs and answers it comprehensively and positively. The sentence says:

• Every finite simple graph has a straight line representation in . ${\displaystyle \mathbb {R} ^{3}}$

literature

• Lowell W. Knieke, Robin J. Wilson (Eds.): Graph Connections . Relationships between Graph Theory and other Areas of Mathematics (=  Oxford Lecture Series in Mathematics and its Applications . Volume 5 ). Clarendon Press, Oxford 1997, ISBN 0-19-851497-2 ( MR1634542 ).
• Lowell W. Knieke, Robin J. Wilson (Eds.): Topics in Topological Graph Theory (=  Encyclopedia of Mathematics and its Applications . Volume 128 ). Cambridge University Press, Cambridge 2009, ISBN 978-0-521-80230-7 ( MR2581536 ).
• Rudolf Fritsch : The four-color set. History, topological foundations and idea of ​​proof . With the collaboration of Gerda Fritsch . BI Wissenschaftsverlag, Mannheim / Leipzig / Vienna / Zurich 1994, ISBN 3-411-15141-2 ( MR1270673 ).
• Jonathan L. Gross, Thomas W. Tucker: Topological Graph Theory (=  Wiley Interscience Series in Discrete Mathematics and Optimization ). John Wiley & Sons, New York 1987, ISBN 0-471-04926-3 , pp. 201-224 ( MR0898434 ).
• Jonathan L. Gross, Jay Yellen (Eds.): Handbook of Graph Theory (=  Discrete Mathematics and its Applications ). CRC Press , Boca Raton (et al.) 2004, ISBN 1-58488-090-2 , pp. 610-786 .
• Branko Grünbaum : Polytopal Graphs in: Studies in Graph Theory. Part II (Ed. DR Fulkerson ) (=  Studies in Mathematics . Volume 12 ). Mathematical Association of America , Washington, DC 1975, ISBN 0-88385-112-1 , pp. 201-224 ( MR0406868 MR0392630 ).
• Rudolf Halin : Graph Theory I (=  yields of research . Volume 138 ). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).
• Nora Hartsfield, Gerhard Ringel : Pearls in Graph Theory. A Comprehensive Introduction . Academic Press, Boston (et al.) 1990, ISBN 0-12-328552-6 ( MR1069559 ).
• Dénes König : Theory of finite and infinite graphs . Combinatorial topology of the route complexes. Academic Publishing Company, Leipzig 1936.
• Gerhard Ringel: Map Color Theorem (=  The basic teachings of the mathematical sciences in individual representations . Volume 209 ). Springer Verlag, Berlin / Heidelberg / New York 1974 ( MR0349461 ).
• H. Sachs : Commentary appendix (part 12) in: D. Kőnig: Theory of finite and infinite graphs (Hrsg. H. Sachs) (=  Teubner Archive for Mathematics . Volume 6 ). BSB BG Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 , p. 326-327 ( MR0886676 ).
• Lutz Volkmann: Foundations of the graph theory . Springer Verlag, Vienna / New York 1996, ISBN 3-211-82774-9 ( MR1392955 ).
• Klaus Wagner : Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim (inter alia) 1970, ISBN 3-411-00248-4 .
• Arthur T. White: Graphs, Groups and Surfaces (=  North-Holland Mathematics Studies . Volume 8 ). 2nd Edition. North-Holland Publishing Company, Amsterdam 1984, ISBN 0-444-87643-X . MR0780555

Individual evidence

1. ^ Rudolf Halin: Graph Theory I. 1980, p. 39