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 5sphere implies that EMBED d→d and EMBED(d1)→d are undecidable for each d ≥ 5. Our main result is NPhardness 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; NPhardness; Piecewise linear; Planarity

Conference Title:

SODA: Symposium on Discrete Algorithms

Conference Dates:

January 46, 2009

Conference Location:

New York, NY, USA

ISBN:

15579468

Publisher:

SIAM

Date Published:

20090101

Start Page: 
855

End Page:

864

URL: 

Open access: 
yes (repository) 