University of Arkansas Topology Seminar: 9/14/2017

Speaker: Yo'av Rieck

Title: Embeddability of 2– and 3–complexes in ℝ³ 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):

1. d = 1: is farily easy to see that this is linear.
2. 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).
3. d = 2, k = 2: decidable in linear time (J Gross and R Rosen 1979).
4. d ≥ 4, k < (2d−2)/3: decidable in polynomial time.
5. d ≥ 4, k ≥ (2d−2)/3: NP-hard (Matoušek, Tancer and Wagner 2011).
6. 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.