A characterization of plane Gauss paragraphs

Abstract

Gauss first studied representations of self-intersecting curves in the plane using only lists of their crossings in the sequence as they occur when traversing a curve, i.e., representations using Gauss words. The characterisation of words that are Gauss words has been elusive for a long time, and only in recent decades have some good characterizations been established. Together with these, the interest in Gauss paragraphs, i.e., representations of sets of curves by sets of words listing their sequences of crossings, has came to light, and we are unaware of a (good) characterization of abstract sets of words that are Gauss paragraphs. We establish such a characterization and we show that characterizing Gauss paragraphs is algorithmically equivalent to characterizing Gauss words, as there exists a word W that can be obtained from a set of words P in linear time, such that P is a Gauss paragraph if and only if W is a Gauss word.