University of Arkansas Topology Seminar: 9/14/2017
Speaker: Yo'av Rieck
Title: Embeddability of 2– and 3–complexes in ℝ3 is NP-hard
Abstract: for positive integers d ≥ k, consider the following decision problem: given a (finite) k–complex X, does X embed in ℝd? This generalizes graph planarity, which is the case k = 1, d = 2. Known results exhibit a variety of phenomena (a few references are listed):
- d = 1: is farily easy to see that this is linear.
- d = 2, k = 1 (graph planarity): decidable in linear time (the original algorithm is due to Hopcroft and Tarjan 1974, but has been simplified significantly since).
- d = 2, k = 2: decidable in linear time (J Gross and R Rosen 1979).
- d ≥ 4, k < (2d−2)/3: decidable in polynomial time.
- d ≥ 4, k ≥ (2d−2)/3: NP-hard (Matoušek, Tancer and Wagner 2011).
- d ≥ 5, k = d or k = d−1: undecidable (Matoušek, Tancer and Wagner 2011).
This leaves wide open the cases d = 3 and k = 2, k = 3. Recently, Matoušek, Sedgwick, Tancer, and Wagner showed that this problem is decidable and, moreover, the two problem are equivalent.
In this talk we will show that these cases are NP-hard. This is joint work with Arnaud de Mesmay, Eric Sedgwick, and Martin Tancer.
BACK TO SCHEDULE