OneDimensional Computational Topology
Announcements
 Feb 2


The paper chase assignment is due Tuesday, February 28. (I've updated the list of suggested strting points to include only papers published in 2021 or later.) This is the first part of the semester project.

Starting next week, I will have office hours every Tuesday 34. (I'm also usually free immediately after class on Wednesday and Friday.)
 Jan 8
 Hello and welcome! I'm still setting up the class; please forgive the dust, construction noises, and dead links. First some logistics:
 Formally, registration is currently restricted to graduate students in computer science.

Graduate students in other fields, especially mathematics, are definitely welcome. Registration should open to nonCS graduate students by the end of the day on January 9, but this is a manual process driven by overworked academic office staff, so please be patient. Please talk to me after class if you are still unable to register by the end of the first week (January 20).

Undergraduates interested in taking this course should submit a petition to register as soon as possible, but absolutely no later than January 20. Petitions can take several weeks to process (because they must be processed individually by overworked academic office staff).
 We are using Ed Discussion site as an online discussion forum. You can enroll yourself using your university login credentials; no enrollment code is necessary.
 I plan to maintain a list of "homework" exercises. At least for now, these are meant only for your practice and understanding; homework will not be graded. I strongly encourage discussing these exercises (and any similar problems that occur to you) on Ed Discussion.
About this class
This course is an introduction to my favorite facet of computational topology: Algorithms for curves and graphs embedded in the plane or other surfaces. Algorithmic questions about curves have been a driving force in topology since its inception more than a century ago. Planar and nearplanar graphs have long been fertile ground for algorithms research, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs. There is a rich interplay between these two domains, drawing on a common pool of techniques from geometry, topology, and combinatorics. Potential topics include topological graph theory; homotopy, homology, and other topological invariants; specialized algorithms for shortest paths, maximum flows, and minimum cuts; efficient approximation schemes for NPhard problems; and applications in VLSI design, computer graphics, computer vision, motion planning, geographic information systems, and other areas of computing. Specific topics will depend on the interest and expertise of the students.
Students in all areas of computer science, mathematics, and related disciplines are welcome. CS 473 and/or Math 525 are recommended as prerequisites, but not required; necessary background material will be introduced as needed. Undergraduates interested in taking this course should petition for a registration override as soon as possible.
This course does not satisfy the "Theory and Algorithms" breadth requirement for MCS and MS students, but it can be used to satisfy the Advanced Coursework requirement.
Historical Gallery
A Möbiusband chain pump. AlJazari,
Book of Knowledge of Ingenious Mechanical Devices (1206)
Nonagonus secundi ordinis. Thomas Bradwardine,
Geometria speculativa (c.1320)
The first maze. Giovanni Fontana,
Bellicorum instrumentorum liber cum figuris (c.1420)
An unfolding of a snub cube. Albrecht Dürer,
Underweysung der messung (1520)
Computing the area of a nonconvex polygon. Albrecht Meister,
Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus (1770)
A simple closed curve. Bernard Bolzano,
Die drey Probleme der Rectification, der Complanation und der Cubirung (1817)
Decomposing a nonsimple curve into simple curves. Carl Friedrich Gauß,
Zur Geometria situs (Nachlass) (c.1830)
Proving that every convex(!) polygon can be triangulated. Carl Friedrich Gauß,
Zur Geometria situs (Nachlass) (c.1830)
A system of cycles and its dual system of arcs on a punctured torus. Bernhard Riemann,
Theorie der Abel'schen Functionen (1857)
A pants decomposition. Johann Benedict Listing,
Census Räumlicher Complexe (1862)
"Alexander" numbering of a nonsimple polygon. Johann Benedict Listing,
Vorstudien von Topologie (1847)
Cutting a surface at noncritical heights. August Möbius,
Theorie dr elementaren Verwandtschaft (1863)
A reciprocal pair of form/force diagrams. James Clerk Maxwell,
On reciprocal figures and diagrams of forces (1864)
Flipping an edge in a triangulation. August Möbius,
Ueber die Bestimmung des Inhalts eines Polyëders (1865)
The "MorseSmale" complex of a smooth terrain. James Clerk Maxwell,
On Hills and Dales (1870)
A planar map and its dual, specified by the same rotation system. Max Brückner,
Vielecke und Vielflache: Theorie und Geschichte (1900)
Paul Klee,
Pedagocial Sketchbook (1925), English translation by Sybil MoholyNagy (1953)
The "treeonion figure" of a planar map. Max Dehn,
Über kombinatorische Topologie (1936)
Piet Hein's inspirations for the game "Polygon", now known as "Hex". Piet Hein, "Vil de lære Polygon?",
Politiker (December 26, 1942)
Asteroids, developed by Lye Raine, Ed Logg, and Dominic Walsh (1979)
Other computational topology classes
The selection of topics in this class is necessarily limited by the finiteness of a single semester and by my own interests and expertise. Important topics in computational topology that I will not cover this semester, except perhaps briefly in passing, include automatic groups, knot theory, 3manifolds, cell complexes (simplicial, cubical, Delta, CW, simplicial sets), algorithms for CAT(0)complexes, discrete Morse theory, normal surface theory, configuration spaces, dynamical systems, persistent homology and its generalizations, surface reconstruction, manifold learning, topological data analysis, embedding obstructions, higherorder homotopy, discrete differential geometry, applied Hodge theory, fixedpoint theorems, PPADcompleteness, algebraic complexity, $\exists\mathbb{R}$hardness and "Murphy's Law" universality, evasiveness of graph properties, impossibility results in distributed computing, and topological quantum computing. The full diversity of techniques, results, applications, and even definitions of computational topology could easily fill a dozen courses.
Here is an incomplete list of other recent courses in computational topology with publicly available course materials (beyond just a syllabus). Please let me know if you'd like to add your course!

Henry Adams, Colorado State:
Spring 2021
Summer 2017 (Universidad de Costa Rica),
Spring 2017

Luca Castelli Aleardi, Arnaud de Mesmay, and Vincent Pilaud, ENS Paris:
202223
— course notes 1,
course notes 2

HsienChih Chang, Dartmouth:
Fall 2021,
Fall 2020

Frederic Chazal and Julien Tierny, Université de Sorbonne:
Fall 2022

Keenan Crane, CMU:
most recent,
Spring 2022,
Spring 2021
(videos),
Spring 2020
— course materials

Isabel Darcy, University of Iowa:
Fall 2013,
Spring 2015,
Spring 2017,
Spring 2018

Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari, MIT:
Fall 2011

Tamal Dey:
Spring 2021 (Purdue),
Fall 2013 (OSU) —
textbook (with Yusu Wang)

Kyle Fox, UT Dallas:
Fall 2020

Leo Guibas, Stanford:
Spring 2021

Spike Hughes, Brown University:
Spring 2015

Misha Kazhdan, Johns Hopkins:
Fall 2009

Philip Klein, Brown University:
Spring 2017
— book draft (with Shay Mozes)

Bala Krishnamoorthy, Washington State University:
Spring 2022,
Spring 2016

Francis Lazarus and Arnaud de Mesmay, Université de Grenoble and ENS Lyon:
Fall 2016

Shay Mozes, Reichman University:
Fall 2015

Vidit Nanda, Oxford:
Hilary 2022

Bradley Nelson, University of Chicago:
Winter 2022

Steve Oudot, École polytechnique:
202223

Bei Wang Phillips, Utah:
Spring 2021,
Spring 2019,
Spring 2017

Michael Robinson, American University:
Spring 2016

Hal Schenk, Auburn:
Summer 2020 —
textbook draft

Yusu Wang, UCSD:
Spring 2022