CS 598: Computational Topology (Fall 2009)

 ❖  About  ❖  Schedule  ❖  References  ❖  Coursework  ❖  Projects  ❖ 

Schedule

Lecture notes are available for some topics—look for links in the left margin. Most of these notes are sketchy; most (if not all) of them are also buggy. Feedback is welcome, especially if you find mistakes!

 ❖  Introduction  ❖  Paths in the plane  ❖  Curves on surfaces  ❖ 
 ❖  Topological graph theory  ❖  Normal curves and surfaces  ❖  Homology  ❖ 

 ❖  This week's lecture  ❖  Future Topics  ❖  Related Topics  ❖ 

Introduction

Tue, Aug 25
no notes

The Seven Bridges of Königsberg and two other bridge systems.
From Euler [Commentarii 1735]

Introduction, history, overview, and administrivia.

• Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8:128–140, 1741. Presented to the St. Petersburg Academy on August 26, 1735. Reprinted in Opera Omnia 1(7):1–10. [The famous Königsberg bridge paper, arguably the first published result in topology. Only proves that a graph with more than two odd vertices has no Euler tour. The paper also very briefly sketches the first topological algorithm—computing an Euler tour in a graph with at most two odd vertices.]
• Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6:30–32, 1873. [The first proof of that a graph with at most two odd vertices has an Euler tour, given in the form of an algorithm. Hierholzer attributes the main ideas to Listing's 1847 treatise Volesung zur Topologie.]
• Henri Poincaré. Analysis situs. Journal de l'École Polytechnique 1:1–121, 1895. Reprinted in Ouvres VI:193–288. [The beginnings of topology in its modern form.]
• Henri Poincaré. Second complément à l'analysis situs. Proceedings of the London Mathematical Society 32:277–308, 1900. Reprinted in Ouvres VI:338–370. [Includes, among many other results, the standard algorithm for computing the Betti numbers of a simplicial complex, via elementary row and column operations, starting with the boundary matrices. Poincaré was apparently unaware of the equivalent algorithm published by Smith in 1861 to compute the Smith normal form of an integer matrix.]
• Wolfgang Haken. Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten. Acta Mathematica 105:245–375, 1961. [Haken's quadruply-exponential-time algorithm to recognizing whether a given knot is trivial.]

Paths in the plane

Thu, Aug 27
[notes]

A simple polygon.
from Kaplan and Bosch [BRIDGES 2005]

The Jordan-Schönflies Theorem, testing whether a point lies inside a polygon

• W. Randolph Franklin. PNPOLY - Point Inclusion in Polygon Test. 〈http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html〉, May 20, 2008. [A particularly concise implementation of the ray-parity algorithm.]
• Richard Hacker. Certification of Algorithm 112: Position of point relative to polygon. Communications of the ACM 5(12):606, 1962. [Corrects a minor bug in Shimrat's algorithm.]
• Camille Jordan. Courbes continues. Cours d'Analyse de l'École Polytechnique, 587–594, 1887. [The first formal statement and proof of the theorem.]
• Andrew Ranicki. Jordan curve theorem. 〈http://www.maths.ed.ac.uk/~aar/jordan/〉, February 21, 2008. [Pointers to several historical and canonical proofs.]
• Arthur Schönflies. Beiträge zur Theorie der Punktmengen. III. Mathematische Annallen 62:286–328, 1906. [First statement and proof of the Jordan-Schönflied theorem.]
• M. Shimrat. Algorithm 112: Position of point relative to polygon. Communications of the ACM 5(8):434, 1962. [The first publication of the ray-parity algorithm qua algorithm, but almost certainly not the first discovery.]
• Oswald Veblen. Theory on plane curves in non-metrical analysis situs. Transactions of the American Mathematical Society 6:83–98, 1905. [The first univerally-accepted proof of the theorem.]

Tue, Sep 1
[notes]

A path in a planar region and a lift to the universal cover.
From Gao et al. [SOCG 1998]

Path homotopy, contractible, simply connected, covering space, universal cover
Shortest homotopic paths: triangulation, crossing sequences, reduction, sleeve, funnel

• Bernard Chazelle. A theorem on polygon cutting with applications. Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 339–349, 1982. [First description of the funnel algorithm for shortest paths in sleeves; see section 5.1. The main result of the paper is algorithm to find a diagonal that splits any n-gon into two smaller polygons, each with at most 2n/3 vertices, in O(n) time. Applying this algorithm recursively builds a triangulation of the polygon in O(n log n) time.]
• Shaodi Gao, Mark Jerrum, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling, and Christoph Storb. On continuous homotopic one-layer routing. Proceedings of the 4th Annual Symposium on Computational Geometry, 392–402, 1988.
• John Hershberger and Jack Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications 4(2):63–97, 1994. [The algorithm described in class for computing shortest homotopic paths in triangulated polygons with holes in O(nk) time.]
• Der-Tsai Lee and Franco P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks 14:393–410, 1984. [The funnel algorithm again; the paper actually describes an algorithm to compute the tree of shortest paths from any point to all vertices of a simple polygon in O(n log n) time.]
• Charles E. Leiserson and F. M. Maley. Algorithms for routing and testing routability of planar VLSI layouts. Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 69–78, 1985.

Thu, Sep 3
Tue, Sep 8
[notes]

Reduction from Hopcroft's problem to contractibility.
From Cabello et al. [DCG 2004]

Testing homotopy between paths in the punctured plane: sentinel points, monotone paths, vertical ranking, rectified paths, sliding brackets

• Sergei Bespamyatnikh. Computing homotopic shortest paths in the plane. Journal of Algorithms 49:284–303, 2003.
• Sergei Bespamyatnikh. Encoding homotopy of paths in the plane. Proceedings of the 6th Latin American Symposium on Theoretical Informatics , 329–338. Lecture Notes in Computer Science 2976, Springer-Verlag, 2004.
• Sergio Cabello, Yuanxin Liu, Andrea Mantler, and Jack Snoeyink. Testing homotopy for paths in the plane. Discrete & Computational Geometry 31(1):61–81, 2004. [The algorithm described in class to check whether two simple paths are homotopic in the punctured plane in O(n log n) time. Distinguishes between tack, pin, and pushpin models; all followup papers use the pin model.]
• Bernard Chazelle. An algorithm for segment-dragging and its implementation. Algorithmica 3:205–221, 1988. [Describes a data structure for bracket queries. Given a set of n points in the plane, the data structure uses O(n) space, can be built in O(n log n) time, and can answer queries of the following form in O(log n) time: Report the leftmost point, if any, in a three-sided rectangle that is open on the right.]
• Alon Efrat, Stephen Kobourov, and Anna Lubiw. Computing homotopic shortest paths efficiently. Computational Geometry: Theory and Applications 35(3):162–172, 2006.

Thu, Sep 10
[notes]

A buffer of hexahedra around a subdivided tetrahedral mesh.
From Eppstein [CGTA 1999]

Regular homotopy, winding and turning numbers, the Whitney-Graustein theorem, hexahedral meshing, cube complexes for balls

• Marshall Bern, David Eppstein, and Jeff Erickson. Flipping cubical meshes. Engineering with Computers 18(3):173-187, 2002.
• David Eppstein. Linear complexity hexahedral mesh generation. Computational Geometry: Theory & Applications 12:3–16, 1999.
• Kurt Mehlhorn and Chee-Keng Yap. Constructive Whitney-Graustein theorem: or how to untangle closed planar curves. SIAM Journal on Computing 20(4):603–621, 1991. [Given two polygons with the same turning number, constructs a regular homotopy from one to the otehr consisting of O(n²) vertex translations. One of the first computational topology papers from the computational geometry community.]
• Scott A. Mitchell. A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS `96), 456–476. Lecture Notes in Computer Science 1046, Springer, 1996. [Proves that any even quad mesh of the sphere can be extended to a hex mesh of the enclosed ball.]
• Peter Murdoch, Steven Benzley, Ted Blacker, and Scott A. Mitchell. The spatial twist continuum: A connectivity based method for representing all-hexahedral finite element meshes. Finite Elements in Analysis and Design 28:137-149, 1997. [Investigates the arrangement of surfaces dual to any hexahedral mesh.]
• Tahl Nowik. Complexity of planar and spherical curves. Duke Journal of Mathematics 148(1):107–118, 2009. [Given two regular curves on the plane or the sphere, each with at most n self-intersection points, Θ(n²) Whitney moves are always sufficient and sometimes necessary to transform one curve into the other.]
• William P. Thurston. Hexahedral decomposition of polyhedra. Posting to sci.math, October 25, 1993. [Proves that any even quad mesh of the sphere can be extended to a hex mesh of the enclosed ball.]
• Gert Vegter. Kink-free deformation of polygons. Proceedings of the 5th Annual Symposium on Computational Geometry, 61–68, 1989. [Given two polygons with the same turning number, constructs a regular homotopy from one to the otehr consisting of O(n) vertex translations.]
• Hassler Whitney. On regular closed curves in the plane. Compositio Mathematica 4:276–284, 1937.

Curves on Surfaces

Tue, Sep 15
[notes]
HW 1 released

A polygonal schema dual to an embedding of K₇ on the torus.
from Heffter [Math. Ann. 1891]

combinatorial 2-manifolds, polygonal schemas, rotation systems, barycentric subdivision, duality, equivalence with topological 2-manifolds

• Max Dehn and Poul Heegaard. Analysis situs. Enzyklopädie der mathematischen Wissenschaften mit Einschluß ihrer Anwendungen III.AB(3):153–220, 1907. [The first formal development of combinatorial topology. Defines surfaces as the underlying space of a schema of triangles.]
• Jack Edmonds. A combinatorial representation for polyhedral surfaces. Notices of the American Mathematical Society 7:646, 1960. [Proposes (unsigned) rotation systems for simple graphs on orientable surfaces.]
• Jonathan L. Gross and Seth R. Alpert. The topological theory of current graphs. Journal of Combinatorial Theory, Series B 17:218–233, 1974. [Generalized rotation systems to multigraphs, by storing permutations of edges instead of permutations of neightbors.]
• Lothar Heffter. Über das Problem der Nachbargebiete. Mathematische Annalen 38(4):477–508, 1891. [Used polygonal schemata to study colorability of graphs on surfaces.]
• Béla Kerékjártó. Vorlesung über Topologie. Springer-Verlag, 1923. [Proved that every topological 2-manifold has a triangulation, independently of Radó.]
• Tibor Radó. Über den Begriff der Riemannschen Fläche. Acta Litterarum ac Scientiarum, Szeged 2:101–121, 1925. [Proved that every topological 2-manifold has a triangulation, independently of Kerékjártó.]

Thu, Sep 17
[notes]

Dyck's surface Σ(1,1)=Σ(0,3).
adapted from Dyck
[Math. Ann. 1888]

surface classification, attaching handles and Möbius bands, contracting and deleting edges, tree-cotree decomposition, system of loops, “Oilers' formula”

• James W. Alexander, II. Normal forms for one- and two-sided surfaces. Annals of Mathematics, Second Series 16(1/4):158–161, 1914-1915. [Defined the now-standard canonical polygonal schemata for surfaces used in Brahana's proof, and sketches a proof that any polygonal schema can be transformed into a canonical schema. Alexander calls the canonical schema for orientable surfaces (aba'b'cdc'd'...) “well-known”.]
• Henry R. Brahana. Systems of circuits on two-dimensional manifolds. Annals of Mathematics 23(2):144–168, 1922. [The first universally acknowledged proof of the (combinatorial) surface classification theorem. This is the proof that appears in almost every topology textbook.]
• Max Dehn and Poul Heegaard. Analysis situs. Enzyklopädie der mathematischen Wissenschaften mit Einschluß ihrer Anwendungen III.AB(3):153–220, 1907. [The first formal development of combinatorial topology. Includes a (sketchy) proof of the (combinatorial) surface classification theorem.]
• Walther von Dyck. Beiträge zur Analysis situs I. Aufsatz. Ein- und zweidimensionale Mannigfaltigkeiten. Mathematische Annalen 32(4):457–512, 1888. [The first complete statement of the (combinatorial) surface classification theorem. The classification of orientable surfaces was already known (but not proved) by Riemann (1851), Möbius (1863), Jordan (1866), and Klein (1882), among others.]
• Simon A. J. l'Huilier. Démonstration immédiate d'un théorème fondamental d'Euler sur les polyhèdres, et exception dont ce théorème est susceptible. Mémoires de l'Académie Impériale des Sciences de Saint-Petersbourg 4:271–301, 1811. [The first generalization of Euler's formula to polyhedra with non-zero genus: V-E+F=2-2g.]
• Carsten Thomassen. The Jordan-Schönflies theorem and the classification of surfaces. The American Mathematical Monthly 99(2):116–131, 1992. [A completely self-contained proof of the surface classification theorem, including proofs of the necessary portions of the Jordan-Schönflies and Kerékjártó-Radó theorems.]
• George Francis and Jeff Weeks. Conway's ZIP proof. The American Mathematical Monthly 106(5):393–399, 1999. [A short proof of the (combinatorial) surface classification theorem. Despite its name, the proof includes a few irrelevancies.]
• Gert Vegter and Chee-Keng Yap. Computational complexity of combinatorial surfaces. Proceedings of the 6th Annual Symposium on Computational geometry, 102–111, 1990. [Brahana's proof can be transformed into an algorithm to transform any system of loops into a canonical system of loops (as defined by Alexander) in O(g²) time. Vegter and Yap improve the running time to O(g log g) using a more careful choice of transformations and data structures.]

Tue, Sep 22
Thu, Sep 24
[notes]

The Cayley graph of the fundamental group of the double torus.
From Yann Oliver

fundamental groups, group presentations, one-relator presentation from any system of loops, universal covers, hyperbolic tilings, Dehn's contractibility algorithm, compressed crossing sequences

• Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen 71(1):16–144, 1911. [Describes the word problem, the conjugacy problem, and the isomorphism problem for infinite discrete groups.]
• Max Dehn. Transformation der Kurven auf zweiseitigen Flächen. Mathematische Annalen 72(3):413–421, 1912. [Solves the word problem and the conjugacy problem for fundamental groups of orientable 2-manifolds, using hyperbolic geometry. One of the foundational results of combinatorial group theory.]
• Tamal K. Dey and Sumanta Guha. Transforming curves on surfaces. Journal of Computer and System Sciences 58:297–325, 1999. [Describes linear-time algorithms to determine whether a cycle on an combinatorial surface is contractible (the word problem in the fundamental group), or whether two cycles are freely homotopic (the conjugacy problem)]
• Martin D. Greendlinger. Dehn's algorithm for the word problem. Communications in Pure and Applied Mathematics 13:67–83, 1960. [Generalizes Dehn's algorithm for the word problem to abstract groups satisfying a certain small cancellation condition C(1/6).]
• Martin D. Greendlinger. On Dehn's algorithm for the conjugacy and word problems with applications. Communications in Pure and Applied Mathematics 13:641–677, 1960. [Generalizes Dehn's algorithm for the conjugacy problem to abstract groups satisfying a certain small cancellation condition C'(1/8).]
• Arye Juhàsz. Solution of the conjugacy problem in one-relator groups. Algorithms and Classification in Combinatorial Group Theory (Gilbert Baumslag and Charles F. Miller III, editors), 69–81. Mathematical Science Research Institute Publications 23, Springer, 1992.
• Roger D. Lyndon and Paul E. Schupp. Combinatorial Group Theory. Springer-Verlag, 2001. [The standard textbook.]
• Walter Magnus. Das Identitätsproblem für Gruppen mit einer definierenden Relation. Mathematische Annalen 106(1):295–307, 1932. [Solves the word problem for arbitrary groups with a one-relator presentation.]

Tue, Sep 29
Thu, Oct 1
[notes]

The shortest splitting cycle can cross a shortest path Ω(g) times.
From Chambers et al.
[CGTA 2008]

shortest non-contractible cycles, three-path condition, modified Dijkstra, crossing shortest paths, cutting into disks, cut graphs, crossing sequences

• Sergio Cabello. Many distances in planar graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 1213–1220, 2006.
• Sergio Cabello and Erin W. Chambers. Multiple source shortest paths in a genus g graph. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 89–97, 2007.
• Sergio Cabello and Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete & Computational Geometry 37(2):213–235, 2007.
• Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry 31:37–59, 2004.
• Jeff Erickson and Kim Whittlesey. Greedy optimal homotopy and homology generators. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 1038–1046, 2005.
• Greg Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16(6):1004–1022, 1987.
• Martin Kutz. Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. Proceedings of the 22nd Annual Symposium on Computational Geometry, 430–438, 2006.
• Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. Journal of Combinatorial Theory, Series B 48:155–177, 1990.
• John Reif. Minimum s-t cut of a planar undirected network in O(n log²(n)) time. SIAM Journal on Computing 12(1):71–81, 1983.

Tue, Oct 6
Thu, Oct 8
no notes
(see paper)

Two cycles on a double-torus.
From Chambers et al.
[SoCG 2009]

minimum cuts in surface graphs: boundary subgraphs, ℤ₂-homology, shortest-path crossing bounds, crossing (parity) vectors, weighted triangulations

• Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. Proceedings of the 25th Annual Symposium on Computational Geometry, 377–385, 2009.
• Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Splitting (complicated) surfaces is hard. Computational Geometry: Theory & Applications 41(1-2):94–110, 2008.

Topological graph theory

Tue, Oct 13
Thu, Oct 15
[notes]
HW2 released

A small balanced separator of a planar graph.
From Ken Stephenson

graph separators: Menger's theorem, planar graphs, disk packing, center points, greedy tree-cotree decomposition, level slicing

• Michael O. Albertson and Joan P. Hutchinson. On the independence ratio of a graph. Journal of Graph Theory 2(1):1–8, 1978.
• Lyudmil Aleksandrov and Hristo Djidjev. Linear algorithms for partitioning embedded graphs of bounded genus. SIAM Journal on Discrete Mathematics 9(1):129–150, 1996.
• Noga Alon, Paul Seymour, and Robin Thomas. Planar separators. SIAM Journal on Discrete Mathematics 7(4):184–193, 1994.
• E. M. Andreev. Convex polyhedra in Lobačevskiĭ space. Math. USSR Sbornik 10:413–440, 1970.
• E. M. Andreev. On convex polyhedra of finite volume in Lobačevskiĭspace. Math. USSR Sbornik 12(2):270–259, 1970.
  
  
  Cutting a surface into slices.
  From Hutchinson
  [SIDM 1998]
• Hristo N. Djidjev. A separator theorem. Comptes Rendus de l' Académie Bulgare des Sciences 34:643–645, 1981.
• David Eppstein. Dynamic generators of topologically embedded graphs. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 599–608, 2003.
• John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms 5(3):391–407, 1984.
• Paul Koebe. Kontaktprobleme der Konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften, Leipzig, Math.-Phys. Klasse 88:141–164, 1936.
• Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36(2):177–189, 1979.
• Kurt Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematica 10:96–115, 1927.
• Warren D. Smith and Nicolas C. Wormald. Geometric separator theorems and applications. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 232–243, 1998.
• Dan Spielman and Shang-Hua Teng. Disk packings and planar separators. Proceedings of the 12th Annual Symposium on Computational Geometry, 349–358, 1996.

Tue, Oct 20
[notes]

A tree decomposition for a planar triangulation.
From Eppstein [JGAA 1999]

tree decompositions, treewidth, Baker's slicing technique, treewidth vs. diameter, PTAS for maximum independent set

• Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for {NP}-hard problems restricted to partial k-trees. Discrete Applied Mathematics 23:11–24, 1989.
• Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery 41(1):153–180, 1994.
• Umberto Bertelè and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, New York, 1972.
• Hans L. Bodlaender. A linear-time algorithm for finding tree-decomposition of small treewidth. SIAM Journal on Computing 25:1305--1317, 1996.
• David Eppstein. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3(3):1—27, 1999.
• David Eppstein. Diameter and treewidth in minor-closed families. Algorithmica 27:275—291, 2000.
• Neil Robertson and Paul D Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 7(3):309–322, 1986.

Thu, Oct 22
[notes]

Interlaced parallel bundles.
From Vollmerhaus 1987

Graph minors: definitions, Kuratowski-Wagner, examples, the Graph Minor Theorem, minor-closed families, finite obstruction sets, membership algorithm, combinatorial properties, planar minor or bounded treewidth, decomposition theorem, lots of references but no proofs

• Noga Alon, Paul D. Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3(4):801–808, 1990.
• Erik D. Demaine and MohammadTaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28(1):19--36, 2008.
• Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 637–646, 2005.
• Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. Journal of Combinatorial Theory, Series B 91(1):25--41, 2004.
• Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4(4):307--316, 1984.
  
  
  
  The obstruction set for torus graphs with no K_3,3 minor.
  From Gagarin et al. 2005
• Casimir Kuratowski. Sur the problème des courbes gauches en Topologie. Fundamenta Mathematicae 15:271–283, 1930.
• Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 462–470, 1994.
• Neil Robertson and Paul D. Seymour. Generalizing Kuratowski's theorem. Congressus Numerantum 45:129–138, 1984.
• Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B 41(1):92–114, 1986.
• Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63:65–110, 1995.
• Neil Robertson and Paul D. Seymour. Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B 89:43–76, 2003.
• Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner's conjecture. Journal of Combinatorial Theory, Series B 92:325--357, 2004.
• Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B 62(2):232–348, 1994.
• Neil Robertson, Paul D. Seymour, and Robin Thomas. Sachs' linkless embedding conjecture. Journal of Combinatorial Theory, Series B 64(2):185–227, 1995.
• Andrew Thomason. The extremal function for complete minors. Journal of Combinatorial Theory, Series B 81(2):318--338, 2001.
• Kurt Wagner. Über eine Erweiterung des Satzes von Kuratowski. Deutsche Mathematik 2:280–285, 1937.

Normal curves and surfaces

Tue, Oct 27
Thu, Oct 29
[notes]

Representatives of two isotopy classes of curves.
From Schaefer et al.
[CCCG 2008]

Normal curves, corner and edge coordinates, exponential compression, straight-line programs, word equations, testing connectivity, counting components, testing isotopy

• Ian Agol, Joel Hass, and William P. Thurston. The computational complexity of knot genus and spanning area. Transactions of the American Mathematical Society 358(9):3821–3850, 2006.
• Wolfgang Haken. Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten. Acta Mathematica 105:245–375, 1961.
• Helmuth Kneser. Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht der Deutscher Mathematiker-Vereinigung 38:248–260, 1929.
• Markus Lohrey. Word problems and membership problems on compressed words. SIAM Journal on Computing 35(5):1210–1240, 2006.
• Masamichi Miyazaki, Ayumi Shinohara, Masayuki Takeda. An improved pattern matching algorithm for strings in terms of straight-line programs. Journal of Discrete Algorithms 1(1):187–204, 2000.
• Wojciech Plandowski and Wojciech Rytter. Application of Lempel-Ziv encodings to the solution of word equations. Proceedings of the 25th International Conference on Automata, Languages, and Programming, 731–742, 1998. Lecture Notes in Computer Science 1443, Springer-Verlag.
• Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Algorithms for normal curves and surfaces. Proceedings of the 8th International Conference on Computing and Combinatorics, 370–380. Lecture Notes in Computer Science 2387, Springer, 2002.
• Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Computing Dehn twists and geometric intersection numbers in polynomial time. Proceedings of the 20th Canadian Conference on Computational Geometry, 111–114, 2008. Full version available as Technical Report 05-009, Computer Science Department, DePaul University, April 2005.
• Saul Schleimer. Polynomial-time word problems. Commentarii Mathematici Helvetici 83(4):741–765, 2008.

Tue, Nov 4
[notes]

Wolfgang Haken's “Gordian unknot”
From Ian Agol

Normal surfaces, knots, ambient isotopy, spanning disk, triangulating knot manifolds, Haken normal cone, fundamental surfaces, vertex surfaces, unknot ∈ NP

• Ian Agol, Joel Hass, and William P. Thurston. The computational complexity of knot genus and spanning area. Transactions of the American Mathematical Society 358(9):3821–3850, 2006.
• Max Dehn. Über die Topologie des dreidimensionalen Raumes. Mathematische Annalen. 69(1):137–168, 1910.
• Wolfgang Haken. Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten. Acta Mathematica 105:245–375, 1961.
• Masao Hara, Seiichi Tani, and Makoto Yamamoto. UNKNOTTING is in AM ∩ co-AM. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 359–364, 2005.
  
  
  “Unknot” by James Siena (2005)
• Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger. The computational complexity of knot and link problems. Journal of the ACM 46(2):185–211, 1999.
• William Jaco and Jeffrey L. Tollefson. Algorithms for the complete decomposition of a closed 3-manifold. Illinois Journal of Mathematics 39(3):358–406, 1995.
• Helmuth Kneser. Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht der Deutscher Mathematiker-Vereinigung 38:248–260, 1929.
• Christos D. Papakyriakopoulos. On Dehn’s lemma and the asphericity of knots. Annals of Mathematics 66:1–26, 1957.
• Michael O. Rabin. Recursive unsolvability of group-theoretic problems. Annals of Mathematics 67:172–194, 1958.
• Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Algorithms for normal curves and surfaces. Proceedings of the 8th International Conference on Computing and Combinatorics, 370–380. Lecture Notes in Computer Science 2387, Springer, 2002.

Project proposals

Thu, Nov 6

Project proposal presentations — no regular lecture

Homology

Tue, Nov 9
[no notes yet]

simplicial and CW-complexes, geometric examples (Rips-Vietoris, Čech, alpha, Delaunay, witness), abstract examples (graph properties, configuration spaces)

Tentative Future Topics

☆

Maximum flows on surface-embedded graphs

☆

Discrete Morse theory, Reeb graphs, Morse-Smale complexes, harmonic quadrangulation

☆

Undecidability results: K(π, 1) complexes of groups

☆

Simplicial/cellular homology: cycles mod boundaries, Smith normal form

☆

Persistent (simplicial/cellular) homology

☆

Zig-zag homology

Related Topics

☆

A point set, its unit-distance graph, its Vietoris-Rips complex, and its shadow.
From Chambers et al.
[SOCG 2008]

Vietoris-Rips complexes and sensor coverage

• Erin W. Chambers, Vin de Silva, Jeff Erickson, and Robert Ghrist. Vietoris-Rips complexes of planar point sets. Discrete & Computational Geometry, in press, 2009.
• Erin W. Chambers, Jeff Erickson, and Pratik Worah. Testing contractibility in planar Rips complexes. Proceedings of the 24th Annual ACM Symposium on Computational Geometry, 251–259, 2008.
• Vin de Silva and Robert Ghrist. Coordinate-free coverage in sensor networks with controlled boundaries via homology. International Journal of Robotics Research 25(12):1205–1222, 2006.
• Vin de Silva and Robert Ghrist. Coverage in sensor networks via persistent homology. Algebraic & Geometric Topology 7:339–358, 2007.
• Alireza Tahbaz-Salehi and Ali Jadbabaie. Distributed computation of a sparse cover in sensor networks without location information. Proceedings of the 42nd Annual Conference on Information Sciences and Systems, 1285d–-1290, 2008.
• Alireza Tahbaz-Salehi and Ali Jadbabaie. Distributed coverage verification in sensor networks without location information. Proceedings of the 47th IEEE Conference on Decision and Control, 4170–4176, 2008.

☆

Surface encoding and compression: Edgebreaker, Schneyder woods

• Luca Castelli Aleardi, Éric Fusy, and Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces, with applications to encoding. Discrete & Computational Geometry 42(3):489–516, 2009.
• Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares. Edgebreaker: A simple compression algorithm for surfaces with handles. Computers & Graphics International Journal 27(4):553–567, 2003.
• Jarek Rossignac. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics 5(1):47–61, 1999.

☆

Knot and link invariants: crossing number, bridge number, twist, writhe, genus, Alexander-Conway, Jones, Homflypt/Flypmoth/Thomflyp/skein