PL-embedding the dual of two Jordan curves into ${\mathbb{S}}^3$ by an $O(n^2)$-algorithm

Abstract

Let be given a {\em colored 3-pseudo-triangulation} ${\mathcal{H}}^{\star }$ with $n$ tetrahedra. Colored means that each tetrahedron have vertices distinctively colored 0,1,2,3. In a {\em pseudo} 3-triangulation the intersection of simplices might be subsets of simplices of smaller dimensions (faces), instead of a single maximal face, as for true triangulations. If ${\mathcal{H}}^{\star }$ is the dual of a cell 3-complex induced (in an specific way to be made clear) by a pair of Jordan curves with $2n$ transversal crossings, then we show that the induced 3-manifold $|{\mathcal{H}}^{\star }|$ is ${\mathbb{S}}^3$ and we make available an $O(n^2$)-algorithm to produce a PL-embedding (\cite{rourke1982introduction}) of ${\mathcal{H}}^{\star }$ into ${\mathbb{S}}^3$. This bound is rather surprising because such PL-embeddings are often of exponential size. This work is the first step towards obtaining, via an $O(n^2)$-algorithm, a framed link presentation inducing the same closed orientable 3-manifold as the one given by a colored pseudo-triangulation. Previous work on this topic appear in \url{http://arxiv.org/abs/1212.0827}, \cite{linsmachadoA2012}, \url{http://arxiv.org/abs/1212.0826}, \cite{linsmachadoB2012} and \url{http://arxiv.org/abs/1211.1953}, \cite{linsmachadoC2012}. However, the exposition and the new proofs of this paper are meant to be entirely self-contained.

27 pages, 25 figures, 17 references. This version is to be submitted to Discrete & Computational Geometry