Hardness of embedding simplicial complexes in ℝd

J. Matoušek, M. Tancer, U. Wagner, in:, SIAM, 2009, pp. 855–864.

Conference Paper | Published
Author
Abstract
Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even if k is not considered fixed). We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED d→d and EMBED(d-1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3.
Publishing Year
Date Published
2009-01-01
Page
855 - 864
Conference
SODA: Symposium on Discrete Algorithms
IST-REx-ID

Cite this

Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in ℝd. In: SIAM; 2009:855-864.
Matoušek, J., Tancer, M., & Wagner, U. (2009). Hardness of embedding simplicial complexes in ℝd (pp. 855–864). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.
Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial Complexes in ℝd,” 855–64. SIAM, 2009.
J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial complexes in ℝd,” presented at the SODA: Symposium on Discrete Algorithms, 2009, pp. 855–864.
Matoušek J, Tancer M, Wagner U. 2009. Hardness of embedding simplicial complexes in ℝd. SODA: Symposium on Discrete Algorithms 855–864.
Matoušek, Jiří, et al. Hardness of Embedding Simplicial Complexes in ℝd. SIAM, 2009, pp. 855–64.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar