A forbidden substructure characterization of Gauss codes
László Lovász, Morris L. Marx · Bulletin of the American Mathematical Society · 1976
considered the following problem. Given a closed curve in the plane which is normal, i.e., it has only finitely many self-intersections and these are transverse double points. Label the crossing points of the curve. The Gauss code of the curve is the word obtained by proceeding along the curve and noting each crossing point label as it is traversed. In the resulting word, every label occurs exactly twice. The problem is to characterize those words which are Gauss codes. Such words will be called here realizable. For a brief history of the work on the problem see [3, pp. 71-73]. In that reference, Grnbaum says, "Solutions of the characterization problem have been found recently (Treybig [5], Marx [4] ); however, they are of the same aesthetically rather unsatisfactory character as Mac Lane's criterion for the planarity of graphs. A characterization of Gauss codes in the spirit of the Kuratowski criterion for planarity of graphs is still missing." This work is an attempt to supply the "missing" criterion. The reader must be the judge of the aesthetic merits. Note that our characterization does meet Edmonds' criterion [1] for a "good characterization".