# Topological and geometric graphs (NDMI095), LS 2016/2017

Jan Kyncl, Pavel Valtr, KAM (contact: surname - at - kam.mff.cuni.cz)
Tuesday at 15:40 in S6

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)

## Topics covered:

#### 28.2. (JK)

• 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

#### 7.3. (JK)

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

#### 14.3. (JK)

• 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)

#### 21.3. (PV)

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

#### 28.3. (JK)

• 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

#### 4.4. (JK)

• The Jordan curve theorem, Thomassen's proof, part 1: the complement of a simple closed curve in the plane has at least two regions. [Lemma 2.1 - Proposition 2.6 in the paper]

#### 18.4. (JK)

• The Jordan curve theorem, Thomassen's proof, part 2: the complement of a simple closed curve in the plane has at most two regions. [Lemma 2.7 - Theorem 2.12 in the paper]

#### 25.4. (PV)

• Turán-type problems for geometric graphs
• The number of edges in a geometric graph with n vertices and no k disjoint edges is at most k^4 n

#### 2.5. (PV)

• The number of edges in a geometric graph with n vertices and no k+1 disjoint edges is at most 2^9 k^2 n

#### 9.5. (PV)

• The number of edges in a geometric graph with n vertices and no k pairwise crossing edges is at most O(R(k,k)^2 n log n). Analogous proof is possible for x-monotone drawings. (Theorem about N-shaped subsequences stated without proof)

#### 16.5. (PV)

• Crossing lemma
• Szemeredi–Trotter theorem about point-line incidences
• The number of lines containing at least k points out of n given points is O(n^2/k^3)
• An upper bound O(n^{4/3}) on the number of unit distances among n points in the plane

#### 23.5. (PV)

• Bisection width
• Stronger crossing lemma for graphs with no C_4 (sketch of proof)