Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/75914
Type: Artigo de periódico
Title: A homological solution for the Gauss code problem in arbitrary surfaces
Author: Lins, S
Oliveira-Lima, E
Silva, V
Abstract: 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.
Subject: gauss code problem
lacets
closed surfaces
4-regular graphs
medial maps (of graphs on surfaces)
face colorability
Country: EUA
Editor: Academic Press Inc Elsevier Science
Rights: fechado
Identifier DOI: 10.1016/j.jctb.2007.08.007
Date Issue: 2008
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000255724700003.pdf238.36 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.