Lecture 11*: Advanced drawings of graphs
Outline
- Topological surfaces, classification
surface as a compact 2-manifold without boundary, orientable and nonorientable surfaces - just a short survey
- Embeddings of graphs on surfaces
surface embedding, faces and Euler's formula, forbidden characterizations of embeddability (everything is very brief and without proofs) - Planar cover and emulator problems
a brief introduction to this very specialized topic
- Graph crossing number
drawing graphs with possible edge crossings, crossing minimization problem
Goals
The goal of this lecture is to show some very basic introduction to topological graph theory, i.e. the branch of GT which deals with drawings of graphs on various surfaces, both from the topological and combinatorial point of view. Though this topic may not sound like a much applicable thing, it has surprisingly deep theoretical and algorithmic consequences (as mentioned already in Lecture 10). Students should learn about what is a "surface", how to embed graphs there and how to recognize embeddability, and finally they will meet the so called crossing number problem.
Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.
Alternative book: [Graphs on surfaces, Mohar - Thomassen: free preview]
Further study: Interested students can take the subject MA051 at FI, focused on interesting advanced topics in topological graph theory.