The majority of the final grade in this course is based on a two-part semester project. The basic requirements of the project are quite open-ended:
Each open problem must combine both topology and algorithms, but it need not be directly related to any of the specific topics covered in class. Students are strongly encouraged to submit problems and work on projects that draw on their prior research experience and interests.
Given a two- or three-dimensional task space, we would like to represent topological and/or geometric equivalence classes of paths using as few bits as possible. The intended application is human-controlled online navigation. A human agent chooses a class of paths by specifying bits in an online fashion; the robotic system would then an appropriate path in the chosen equivalence class. For example, the homotopy class of a path in a polygon with holes can be represented as a sequence of left and right turns in the dual graph of a triangulation. Replacing the holes with sentinel points simplifies the triangulation, leading to a more compact path representation, but at the expense of necessary geometric fidelity. How can we choose a small triangulation that preserves the geometric structure necessary for online navigation?
We would like to track a set of agents moving in a two-dimensional environment (for example, the interior of a polygon with holes) with the help of beam sensors. Each beam sensor is associated with a line segment (called a beam) in the work space. The sensor emits a signal whenever an agent crosses the beam; the signal indicates the direction of the crossing, but not the identity of the agent crossing the beam. The sequence of crossing signals over time defines a sensor word. If there is only one agent and the beams subdivide the environment into disks, we can recover the agent's path (up to homotopy) from the sensor word [Tovar, Cohen, and Lavalle, WAFR 2008]. What information can we extract about the motion of the individual agents from the sensor word? How can we place the beams so that more information can be extracted?
Rather than trying to summarize something I don't understand, let me quote directly from Chris's submission:The objective of this project is to determine what, if any, effect the topology of the underlying slow manifold can be said to have on the killing time, or location of a [stochastic dynamical] system with a two-dimensional slow sub-manifold, and use this information to simplify and accelerate existing simulation techniques. I propose doing this by first considering stochastic diffusion behavior on various 2-manifolds with some killing condition and determine the expected time and distribution of the various homotopy classes of the manifold, and then, if time permits, to adapt this analysis to an actual 3-dimensional dynamical system with a 2-dimensional slow submanifold.
Chvatal's art gallery theorem states that ⌊n/3⌋ point guards are always sufficient and sometimes necessary to guard the interior of any simple n-gon in the plane. O'Rourke proved that ⌈n/2⌉ point guards are always sufficient and sometimes necessary to guard the exterior of a simple n-gon in the plane; this is called the fortress problem. But what if the fortress lives on some other surface? For example, suppose the fortress lies inside a rectangle whose edges are identified to form a torus; then a guard on the north wall of the fortress can see the outside of the south wall, and a guard on the east wall can see the west wall. In this scenario, are ⌊n/3⌋ point guards enough to guard the fortress?In the related prison yard problem, we are required to guard both the interior and exterior of the polygon. A single guard on the boundary of the polygon can see both inside and outside, but cannot see through any other part of the wall. Again, ⌈n/2⌉ point guards are always sufficient and sometimes necessary to guard a planar prison. Can we hire fewer guards if we build our prison on a torus?
Chambers, Erickson, and Nayyeri [STOC 2009] recently developed the first near-linear-time algorithm to compute maximum flows in graphs embedded on higher-genus surfaces. They describe algorithms that run in time O(g7n log 2 n log 2 C), for graphs with integer capacities that sum to C, or in gO(g) n3/2 for arbitrary capacities. Both algorithms are considerably more complicated than the O(n log n)-time planar max-flow algorithm of Borradaile and Klein [JACM 2009].Is there a combinatorial algorithm to compute maximum flows in graphs of constant genus in O(n log n) time? Less ambitiously, is there an algorithm that runs in time O(n log n polylog C) for integer-capacity graphs? The summary describes a few potential lines of attack. For example, is it possible to find a planar subgraph, or a subgraph with constant treewidth, that carries a constant fraction of the flow in near-linear time?
Eppstein, Goodrich, Kim, and Tamstorf considered the problem of partitioning a quadrilateral mesh of an orientable surface into a small number of regular submeshes (connected subsets of a regular square grid). Eppstein et al. proved that partitioning a mesh into the minimum number of regular submeshes is NP-hard; they also described an efficient algorithm based on motorcycle graphs that computes a 24-approximation. Can the approximation factor be improved, either by a new algorithm or tighter analysis of the existing algorithm? Is there a polynomial-time approximation scheme? Is there a similar approximation algorithm for non-orientable meshes?[Motorcycle graphs were named after the light cycles in Tron. Disney is about to release a sequel to Tron, with spiffy new light cycles. The research described in the paper was done at Walt Disney Animation Studios. So there is a nonzero chance that the new light cycle models are quad meshes that have been partitioned into regular submeshes by motorcycle graphs. Are we meta yet?]
A string graph is the intersection graph of a set of simple paths in the plane, called \emph{strings}. Each vertex corresponds to a string, and each edge corresponds to a pair of strings with non-empty intersection; the same pair of strings may cross multiple times. Schaefer, Sedgwick, and Štefankovič [STOC 2002] proved that the planar string-graph problem is in NP. A key technical step in their proof is the observation that any n-vertex string graph has a string representation in which the total number of crossings on each string is at most 2n. (Surprisingly, some string graphs require this many crossings!) The polynomial-time verification algorithm uses Plandowski and Rytter's results on word equations and straight-line programs.The definition of string graphs can be extended to any other 2-manifold, but the results are much weaker. In the same paper, Schaefer, Sedgwick, and Štefankovič prove that the problem of recognizing string graphs on any compact surface is in PSPACE, and any string graph representation requires at most a doubly-exponential number of crossings. Can we reduce the crossing bound to 2poly(n)? If so, the recognition problem for surface string graphs is actually in NP.
Hass, Lagarias, and Pippenger [JACM 1999] proved that the following problems are both in NP, using normal surface theory:After giving both proofs, the authors offer the following remark:
- UNKNOTTING: Given a polygonal knot, is it trivial?
- SPLITTING: Given two polygonal knots, are they linked?
We remark that it is not hard to show that UNKNOTTING is polynomial time reducible to SPLITTING. One can construct a “pushoff” of a knot with zero linking number and check whether the resulting link is split. The answer is “Yes” if and only if the knot is the unknot. We are grateful to the referee for this remark.What are the details of the reduction? Are there similar polynomial-time reductions between other problems involving knots, links, braids, and 3-manifolds?
Let G be a plane graph, and let N be a subset of the faces of G (called nations). The map graph M(G,N) has a vertex for each nation and an edge between two nations if they share a vertex in G. Every planar graph is a map graph, but the converse is not true; indeed, every clique is a map graph. Despite the fact that map graphs do not forbid any fixed minor, Demaine, Hajiaghayi, and Kawarabayashi [Algorithmica 2009] proved that any map graph without an r×r grid minor has treewidth at most O(r3). This result implies fixed-parameter tractable algorithms for certain bidimensional problems on map graphs. Demaine et al. also described map graphs with treewidth r2-1 that contain r×r grid minors. Can this construction be improved to Θ(r3)? If so, this would improve Robertson and Seymour's Ω(r2 log r) lower bound on the worst-case treewidth of an arbitrary graph with an r×r grid minor [Graph Minors V].
Chambers, Erickson, and Nayyeri [SOCG 2009] recently published the first algorithm to compute minimum (s,t)-cuts in undirected graphs of constant genus in O(n log n) time, generalizing earlier results of Reif and Frederickson for planar graphs. Can this algorithm be generalized to directed graphs of constant genus? Even for directed graphs on the torus with unit capacities, the fastest known min-cut algorithm requires O(n3/2 log n) time. Minimum cuts in directed planar graphs can be computed in O(n log n) time, using an algorithm of Janiga and Koubek [Kybernetica 1992], or the more recent max-flow algorithm of Borradaile and Klein [JACM 2009].
Consider the following escape routing problem. We are given two regular point grids of size r×c and r'×c'. A subset of n points within each grid is indexed from 1 to n. Our goal is to find simple, pairwise disjoint paths from each marked point to the boundary of its grid, so that the ordering of the paths match at the grid boundaries. We also require that at most k paths pass between any pair of adjacent pins in each grid. The escape routing problem is similar to other NP-hard routing problems, so it's natural to conjecture that it is also NP-hard. But is it really?As a practical heuristic, suppose we require that the paths out of each grid are monotone, meaning the intersection of any path with any vertical line is either empty or connected. Is there a polynomial-time algorithm for monotonic escape routing, or is this special case still NP-hard? If we are given the ordering of paths on the grid boundaries, a straightforward greedy algorithm computes a routing (if one exists); the problem is finding the right ordering.
A classical problem in graph drawing is to compute an `embedding' (really an immersion) of a given graph into the plane with the minimum possible number of edge crossings. For example, a graph is planar if it can be embedded in the plane with no crossings at all. Computing the so-called crossing number of a graph is NP-hard; however, for any fixed integer k, there is a linear-time algorithm to compute an embedding with at most k crossings, if such an embedding exists. Similarly, finding the minimum-genus surface into which a graph can be embedded with no crossings is NP-hard, but for any fixed integer g, we can decide whether a graph has genus at most g in linear time. We would like to extend these results to other classes of graphs and embeddings. For example, for any fixed integers k and g, can we find an embeddings with at most k crossing in surfaces of genus at most g in linear time? For any fixed integers k and p, can we partition a given graph into p subgraphs, each of which can be embedded in the plane with at most k crossings, in linear time? Are there more efficient algorithms for minimizing the number of crossings in a radial drawing of a bipartite graph?