| [home] - [up] |
Abstract: The usual meaning of a map is a closed surface (orientable or not) with a graph embedded in it. In this way we have a topological object on which a combinatorial structure of vertices, edges and faces is declared. Modifying an idea of Tutte we take the opposite approach: We define a map combinatorially as a set together with three fixpoint- free involutions, satisfying two simple axioms. We then derive easily all familiar notions such as duality, orientability, characteristic, a form of the Jordan curve theorem, and apply it to obtain McLane´s characterization of planar graphs and a solution of the Gauss problem.
Colloquium - 16:00
Abstract: I will discuss sufficient and essentially necessary conditions in terms of the minimum degree for a graph to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3+gamma)|G| contains a triangulation as a spanning subgraph, whereas this need not be the case when the minimum degree is less than 2|G|/3. This is joint work with D. Osthus and A. Taraz.