• Graph terminology, vertices/nodes, edges/arcs; directed and undirected graphs; multiple edges and loops; Graphs with weights; paths; walks; cycles; degree (indegree/outdegree); trees; Eulerian walks, Hamilton tours
• Graph representations:
  • adjacenty matrix and adjacency lists; half-edge data structure
  • different queries on graphs
  • implicit representations: intersection graphs; unit-disk graphs
  • [graph drawing; information visualization; planarity]
• Euler tours
  • Hierholzer's algorithm from 1871. O(m+n) runtime

• Open Eulerian walks.
• Euler tours
  • last-exit tree
  • the BEST theorem of de Bruijn, Ehrenfest, Smith and Tutte
    from 1941/1951, part 1
• depth-first search
  • preorder and postorder

PADS, a library of Python Algorithms and Data Structures implemented by David Eppstein

• connected components in directed and undirected graphs
• condensation of strong components
• k-connectivity, k-edge-connectivity
• biconnected components, blocks and cutvertices, bridges
• testing for biconnectivity via depth-first search using low-pointers
• ear decomposition and open ear decomposition
• s-t-orientation and s-t-numbering

• partition into chains, testing 2-edge-connectivity and 2-connectivity, ear decomposition (Algorithm of Jens M. Schmidt)
• partition into biconnected components (blocks)
• streamlined computation of an s-t-numbering (algorithm of R. E. Tarjan)

• test strong connectivity and partition into strong components, vgl. Überblick von Tarjan und Zwick, 2024
• strong components and leaders
• cycle-finding algorithm
• condensation and acyclicity
• certificate of correctness
• bidirected search algorithm (without proof)

• Flows in networks
  • capacities, conservation of flow, excess, capacities, additivity of excess
  • cuts
  • Max-flow-min-cut theorem
  • residual graph R_f, flow augmentation, augmenting paths
  • algorithm of Ford an Fulkerson
  • characterization of optimality by the residual network.

• Maximum flow by the preflow-push (or push-relabel) algorithm
  • preflow (with corrected definition of excess), active (or overflowing) vertices
  • "height" or "distance" labels d_u
  • admissible arcs
  • general push/relabel operation
  • analysis: labels bounded by 2n
  • saturating and nonsaturating pushes
  • potential function Φ
  • general bound O(mn²)
  • highest label variant: O(n³)
  • Implementation: (a) finding the highest label by bucketing (b) finding an admissible arc
  • practical speedup: periodic breadth-first-search

• preflow-push (or push-relabel) algorithm with the FIFO-queue variant: O(n³)
  • practice: periodic breadth-first-search and the gap heuristic
  • better analysis, leading to O(n²sqrt(m))
• Circulations
  • decomposition into at most m circuit flows
• Multiterminal flows

• applications of the max-flow-min-cut theorem
  • marriage theorem of Philip Hall
  • vertex cover in a bipartite graph: theorem of Dénes Kőnig
• minimum-cost flow: optimality criteria
  • shortest paths with negative-cost edges: the Bellman-Ford algorithm
  • reduced costs

• minimum-cost flow: optimality criteria
  • characterization of graphs without negative cycles
  • reduced costs
• minimum-cost flow: algorithms
  • shortest augmenting paths
  • capacity scaling, see writeup

• minimum cut in undirected graphs, algorithm of Stoer and Wagner
• all-pairs minimum cut in undirected graphs, Gomory-Hu tree
  • submodularity of the cut function

• all-pairs minimum cut in undirected graphs, Gomory-Hu tree
• planar graph, planar maps, doubly-connected edge list
• combinatorial embedding, rotation system

• Euler's formula for plane graphs
• bound m≤3n−6
• maximal plane graphs, or triangulations
• Kuratowski's characterization of planar graphs, Kuratowski subgraphs
  • proof of the necessary part
• chords of face cycles
• triangulating a 2-connected plane graph
• Constructing a straight-line embedding: the shift algorithm of de Fraysseix, Pach, and Pollack
  • canonical order for a triangulated graph
  • frozen edges

• The shift algorithm of de Fraysseix, Pach, and Pollack
  • Addendum: Shifting does not produce crossings
  • Invariant: Shifting the frozen components apart by any positive amounts does not produce crossings.
• Combinatorial surfaces, Euler characteristic
• Schnyder woods and planarity
• • Schnyder woods from canonical orientations

• Schnyder woods:
  • vertex rule
  • outer face rule
  • tree rule (follows from vertex rule)
• Three disjoint paths to the root
• Crossing-free drawing: correctly oriented triangles are enough

• Schnyder woods from 3-orientations
• Storing a graph, testing adjacency, orientations with bounded outdegree
• Degeneracy, density
• Whitney's theorem on unique embeddability for 3-connected planar graphs
  • Characterization of unique face cycles

• Linear-time determination of areas in Schnyder woods
• Whitney's theorem on unique embeddability for 3-connected planar graphs
  • sufficiency
• Outerplanar graphs
• Coloring of k-degenerate graphs
• List coloring of planar graphs, 5-choosable (Thomassen, 1997)
• Planar separator theorem, definition

• Planar separator theorem, construction
  • fundamental cycles
  • breadth-first search

• Vertex elimination and backsubstitution, fill-in
  • shortest paths
  • systems of linear equations
• Generalized nested dissection
  • with separators of size sqrt(n)
  • analysis of the runtime (calculation with all details)
  • variant with linear space

• penny-packing theorem (Ausarbeitung und Folien)

• constructing planar separators from circle packings
  • analysis of the bound on the size of the separators
  • (a chapter from a book by Sariel Har-Peled)
• applications of planar separators:
  • maximum independent set

• testing planarity (python program and description, under development)
  • blocks
  • marking

• testing planarity
  • walkup
  • obstructions
  • walkdown and teardown

• Maximum-cardinality matching
  • Optimality criterion by augmenting paths (Petersen 1891)
  • Alternating trees
  • Shrinking of blossoms
  • Optimality certificate: odd-set cover

• Tutte criterion for perfect matchings
• Petersen's Theorem for bridgeless cubic multigraphs
• Reduction of the general matching problem to graphs with maximum degree 3.
• Weighted perfect matchings, applications
  • Undirected shortest paths
  • The Chinese Postman Problem
  • T-joins
  • The Christofides heuristic for the traveling salesman problem (TSP)

• Perfect matching in cubic bridgeless graphs (Petersen's theorem)
  • Algorithm of Frink (1926, O(n²)), Biedl/Bose/Demaine/Lubiw (2001) and Gawrychowski/Masylkiewicz (2024)
  • Applications: terrain guarding, mesh refinement, quadrangulation
• Maximum independent sets
  • branching algorithms

• Number of maximal independent sets (Moon-Moser)
• Improved branching for maximum independent set
  • domination rule
  • simplicial vertex rule
  • mirror branching
• dynamic programming in trees (example: maximum independent set)
• k-trees

• tree decomposition
• k-trees and tree decompositions
  • smooth tree decompositions
• cliques in tree decompositions
• nice tree decompositions
  • forget nodes, introduction nodes, join nodes
• dynamic programming
  • optimum bisection
• path decomposition and pathwidth

• chromatic number χ, clique number ω, independence number α
  • upper and lower bounds of χ
• perfect graphs
  • mentioned Perfect Graph Theorem and Strong Perfect Graph Conjecture
• chordal graphs
  • contain simplical vertex
  • are perfect
• perfect elimination order
  • iff chordal
  • naïve algorithm for finding a PEO

• perfect elimination order
  • linear-time algorithm for testing a permutation
  • computing a maximum clique
  • computing a χ-coloring
• (stable matching, Gale-Shapley matching)
• (convex bipartite matching)
• (2-machine scheduling)

• dynamic programming
  • number of matchings
  • coloring
  • traveling salesperson problem
• edge colorings of bipartite graphs
• Where is the middle? betweenness index
• inclusion-exclusion techniques
• bipolar orientations