Teaching‎ > ‎

Algorithms & Theory Seminar

Fall 2015/16

Planar Graph Algorithms

A selection of topics:
  • Uniformly random (3-connected) planar graphs
  • Wagner/Kuratowski theorem
  • Recognizing and drawing planar graphs
  • The random planar graph process
  • Geometry: 3-connected planar graphs are 3-dimensional polytopes (Steinitz theorem)
  • Linear time Minimum Spanning Tree
  • Separator Theorem/Algorithm
  • Shortest path algorithms
  • Max-Cut

Spring 2015

Final list of presentations

Digraphs
  • Maximal m-free digraphs
  • Longest paths in tournaments
  • Algorithms for long paths and cycles in digraphs
  • Mod-q cycles via Lovasz's Local Lemma
  • Minimum Cost Branchings and Matroid Intersection
  • Tutte's Matrix-Tree theorem
Random structures
  • "Realistic" probabilistic analysis of sorting algorithms (March 23)
  • Superboolean rank and the largest triangular submatrix of a random matrix (April 27)