Hardness of embedding simplicial complexes in ℝd Conference Paper


Author(s): Matoušek, Jiří; Tancer, Martin; Wagner, Uli
Title: Hardness of embedding simplicial complexes in ℝd
Affiliation
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.
Keywords: Algorithmic problems; Simplicial complex; NP-hardness; Piecewise linear; Planarity
Conference Title: SODA: Symposium on Discrete Algorithms
Conference Dates: January 4-6, 2009
Conference Location: New York, NY, USA
ISBN: 1557-9468
Publisher: SIAM  
Date Published: 2009-01-01
Start Page: 855
End Page: 864
URL:
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
  2. Martin Tancer
    9 Tancer
Related IST Austria Work