A topological framework for signed permutations

In this paper, we present a topological framework for studying signed permutations and their reversal distance. This framework is based on a presentation of orientable and non-orientable fatgraphs via sectors. As an application, we give an alternative approach and interpretation of the Hannenhalli-Pevzner formula for the reversal distance of sorting signed permutations. This is obtained by constructing a bijection between signed permutations and certain equivalence classes of fatgraphs, called π-maps. We study the action of reversals and show that they either splice, glue or half-flip external vertices, which implies that any reversal changes the topological genus by at most one. We show that the lower bound of the reversal distance of a signed permutation equals the topological genus of its π-maps. We then discuss how the new topological model connects to other sorting problems.