A homological solution for the Gauss code problem in arbitrary surfaces

Let (P) over bar be a sequence of length 2n in which each element of {1, 2, ..., n) occurs twice. Let P ' be a closed curve in a closed surface S having n points of simple self-intersections, inducing a 4-regular graph embedded in S which is 2-face colorable. If the sequence of auto-intersections along P ' is given by (P) over bar, we say that P ' is a 2-face colorable solution for the Gauss code (P) over bar on surface S or a lacet for (P) over bar, on S. In this paper we show (by using surface homology theory mod 2), that the set of lacets for (P) over bar on S are in 1-1 correspondence with the tight solutions of a system of quadratic equations over the Galois field GF(2). If S is the 2-sphere, the projective plane or the Klein bottle, the corresponding quadratic systems are equivalent to linear ones. In consequence, algorithmic characterizations for the existence of solutions on these surfaces are available. For the two first surfaces this produces simple proofs of known results. The algorithmic characterization for the existence of solutions on the Klein bottle is new. We provide a polynomial algorithm to resolve the issue. (c) 2007 Elsevier Inc. All rights reserved.98350651