Tuesday at 15:40 in S6

**The lecture will be cancelled on April 11.**

If there is at least one student who does not understand Czech, the lectures will be in English; but you may ask questions in Czech during the lectures.

Entry in SIS, syllabus

**Topics:**

- Introduction: drawings of graphs, topological graphs, geometric graphs
- The Hanani–Tutte theorem (weak, strong, and unified) and an algebraic algorithm for planarity testing
- Thrackles, thrackle conjecture
- The Jordan curve theorem and the nonplanarity of K_{3,3} (Thomassen's proof)
- Crossing numbers of a graph
- Extremal results for topological and geometric graphs without forbidden substructures (k disjoint edges, k crossing edges)

**Literature:** (will be updated during the semester)

- Chapters from lecture notes for Janos Pach's course at EPFL with a partial overlap with this course:
- Chapter 1 - Introduction about drawings of graphs and planar graphs
- Chapter 2 (updated 7. 3. 2017) - Characterizations of planar graphs, Hanani–Tutte theorems, algebraic algorithm for planarity testing
- Chapter 4 - Crossing numbers, thrackles
- Chapter 5 - Extremal results for forbidden crossing edges or disjoint edges

- Unified Hanani–Tutte theorem, updated version (28. 3. 2017) - corrected proof of Case 2
- János Pach and Ethan Sterling, Conway's Conjecture for Monotone Thrackles
- C. Thomassen, The Jordan–Schönflies theorem and the classification of surfaces - An elementary proof of the Jordan curve theorem

- Basic notions: topological graph, simple topological graph, geometric graph, plane graph, planar graph
- Statements of the Jordan curve theorem and the Jordan–Schönflies theorem
- Characterization of planar graphs: statements of Kuratovski's theorem, Wagner's theorem, Euler's formula, upper bound on the number of edges, Fáry's theorem
- Motivating question: what is the maximum possible number of edges in a simple topological graph (or a geometric graph) with no pair of disjoint edges?
- A "very weak" Hanani–Tutte theorem with a sketch of a proof

- The (strong) Hanani–Tutte theorem with a sketch of a proof
- Algebraic algorithm for planarity testing, using the strong Hanani–Tutte theorem

- The weak Hanani–Tutte theorem, two proofs
- Unified Hanani–Tutte theorem, first part of a proof (induction step for graphs with vertex connectivity 0 or 1)

- Thrackle, examples, Conway's thrackle conjecture
- Proof of the thrackle conjecture for geometric thrackles, outerplanar thrackles and monotone thrackles

- Unified Hanani–Tutte theorem: sketch of a proof of the induction step for graphs with vertex connectivity 2, proof for 3-connected graphs
- Basic topological definitions: path-connected set, open set, closed set, interior, closure, boundary; simple polygonal arc, simple polygonal closed curve