Deciding if a shadow resolves into a given link: linear-time algorithms

Abstract

A {\em shadow} (or {\em projection}) is obtained from a link diagram by ignoring the over/under information at each crossing. Given a fixed link $L$ we investigate the complexity of deciding whether an input shadow $S$ can be {\em resolved} into $L$, that is, whether we can assign over/under information to its crossings to obtain a diagram of a link isotopic to $L$. We show that if $L\in \{3_1,4_1,5_1,5_2,6_2,L2a1,L4a1,L5a1,L6n1\}$ then there exists a linear-time algorithm that decides whether an input shadow $S$ resolves into $L$.