Topological and geometric graphs (NDMI095), LS 2025/2026

Jan Kyncl, KAM (contact: kyncl - at - kam.mff.cuni.cz)
Friday at 9:00 in S8

Entry in SIS, syllabus

Topics planned:

• Introduction: drawings of graphs, topological graphs, geometric graphs
• The Hanani–Tutte theorem (weak, strong, and unified) and an algebraic algorithm for planarity testing
• The Jordan curve theorem and the nonplanarity of K_{3,3} (Thomassen's proof)
• Thrackles, thrackle conjecture
• A selection from other topics (extremal results for topological and geometric graphs without forbidden substructures (k disjoint edges, k crossing edges), relations between different types of the crossing number, structural properties of complete topological graphs (a Ramsey-type theorem), linkless embeddings...)

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 - Characterizations of planar graphs, Hanani–Tutte theorems, algebraic algorithm for planarity testing
  • Chapter 4 - Thrackles, crossing numbers
  • Chapter 5 - Extremal results for forbidden crossing edges or disjoint edges
• Unified Hanani–Tutte theorem
• C. Thomassen, The Jordan–Schönflies theorem and the classification of surfaces - An elementary proof of the Jordan curve theorem
• János Pach and Ethan Sterling, Conway's Conjecture for Monotone Thrackles
• Géza Tóth, Note on Geometric Graphs - Upper bound on the number of edges in geometric graphs with no k+1 disjoint edges
• On Geometric Graphs with No k Pairwise Parallel Edges, Graph drawing with no k pairwise crossing edges - Upper bound on the number of edges in geometric graphs with no k pairwise crossing edges

Topics covered:

20.2.

• 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

27.2.

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

6.3.

• The weak Hanani–Tutte theorem, two proofs by redrawing
• Unified Hanani–Tutte theorem, first part of a proof (induction step for graphs with vertex connectivity 0, or 1 for the strong variant)

13.3.

• Unified Hanani–Tutte theorem: proof for connected graphs according to the degree of connectivity
• Basic topological definitions: path-connected set, open set, closed set, interior, closure, boundary; simple polygonal arc, simple polygonal closed curve
• Path-connected components (regions) of an open set in the plane are exactly its connected components (sketch of proof)

20.3.

• The Jordan curve theorem, Thomassen's proof, part 1: planar graphs have polygonal plane drawings, polygonal Jordan curve theorem, extension to polygonal drawings of K_2,3, nonplanarity of K_3,3 [Lemma 2.1 - Lemma 2.5 in the paper]

27.3.

• The complement of a simple closed curve in the plane has at least two regions. [Proposition 2.6]
• The Jordan curve theorem, Thomassen's proof, part 2, including polygonal Euler's formula for 2-connected graphs and the Jordan arc theorem: the complement of a simple arc in the plane is connected. [Lemma 2.7 - Proposition 2.11]

10.4.

• Accessible points from a region, the set of accessible points on a simple closed curve is dense in the curve
• The complement of a simple closed curve in the plane has at most two regions. [Theorem 2.12]
• Thrackle, examples, Conway's thrackle conjecture, overview of known upper bounds
• Proof of the thrackle conjecture for geometric thrackles, exercise for outerplanar thrackles
• Overview of other special cases (annular and pants thrackles, spherical thrackles)
• Exercise: characterize all graphs that can be drawn as geometric thrackles

17.4.

• Proof of the thrackle conjecture for monotone thrackles
• Generalized thrackle, a bipartite graph can be drawn as a generalized thrackle if and only if it is planar
• Corollary: thrackles and generalized thrackles with n vertices have at most 4n edges