Planarity of graphs is a fundamental and well-studied concept.
For instance, Kuratowski's theorem gives a complete characterization
of planar graphs in terms of forbidden, Euler's relation implies precise
upper bounds for the number of edges of a planar graph. On the
computational side, planarity can be tested in linear time, as first shown
by Hopcroft and Tarjan.
Surprisingly little is known about any of the corresponding questions
for higher-dimensional simplicial complexes; What is the computational
complexity of deciding whether a given k-dimensional simplicial complex
K embeds into d-dimensional euclidean space (or the d-sphere)?
Suppose we know that K embeds into d-space, what can we say about
its face numbers?
We will survey some of the known facts and discuss several conjectures (such as the Kalai-Sarkari conjecture) as well as several new results pertaining to these questions.
Joint work with Jiri Matousek, Eran Nevo, Golan Pundak, and Martin Tancer
Copyright. All Rights Reserved.