Department of
Applied
Mathematics

Embeddability of Graphs and 2-dimensional Simplicial Complexes

Rado Fulek

IST Austria

Abstract

A 2-dimensional simplicial complex K is orientably \emph{thickenable} if K embeds into some orientable 3-dimensional manifold which is not fixed in advance. By a result of A. Skopenkov (1994), testing orientable thickenability is in NP, but neither NP-hardness nor the existence of a polynomial time algorithm was established to the best of our knowledge. We show that some constrained variants of planarity testing, whose complexity status is unknown, can be reduced in polynomial time to testing orientable thickenability of 2-dimensional simplicial complexes. Additionally, we present a polynomial time algorithm for orientable thickenability in interesting special cases and discuss possible extensions of our results.

Parts of the talk are based on a joint work with J. Kyncl.