ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 31-36
A characterization of plane Gauss paragraphs
Dan Archdeacon *
Department of Mathematics and Statistics, University of Vermont, Burlington, VT, USA
Drago Bokal, Tanja Gologranc
Faculty of Natural Sciences and Mathematics, University ofMaribor, Slovenia and Institute ofMathematics, Physics and Mechanics, Ljubljana, Slovenia
Received 3 May 2015, accepted 4 November 2015, published online 21 March 2016
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.
Keywords: Gauss words, Gauss codes, Gauss paragraphs, good characterization. Math. Subj. Class.: 5C10, 57M15
1 Introduction
Gauss [5,282-286] has studied representations of closed curves using lists of their crossings in the sequence obtained by following the curve. Clearly, each crossing appears exactly twice, and Gauss noticed that these two occurrences must have one an even and the other an odd index in the sequence, i.e. there has to be an odd number of letters between them. Gauss noted that the condition is not sufficient for curves with five or more crossings. The question of characterizing such words has not been solved until late 1960s, when Marx [9] and
* Written posthumously.
E-mail addresses: drago.bokal@um.si (Drago Bokal), tanja.gologranc@um.si (Tanja Gologranc)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
32
Ars Math. Contemp. 12 (2017) 111-126
Treybig [13] gave algorithmic characterization of words that are Gauss words. Griinbaum [6] noted that they lack the aesthetic appeal of, for instance, Kuratowski theorem, an issue resolved by Lovasz and Marx [8], who gave the first characterization satisfying Edmonds' criterion for "good characterization" [4].
Recently, the interest in Gauss words, i.e. the words that occur when the crossings of a self-intersecting curve are read in a sequence, has been renewed through several new good characterizations [3, 10, 11] and through introduction of Gauss paragraphs, sets of words corresponding in the same manner to sets of curves. The questions that arise in the bibliography are classified by Courcelle [2] into (i) Which (sets of) words over some alphabet are Gauss words (paragraphs), i.e. realizable as (sets of) (self)intersecting curves whose sequences of crossings are equal to specified (sets of) words, (ii) Which (sets of) curves can be uniquely reconstructed from their Gauss words (paragraphs) and (iii) What is the common structure of (sets of) curves having the same Gauss word (paragraph).
In our paper, we investigate the question (i) for Gauss paragraphs, and develop an efficient characterization of sets of words that can be realized with sets of (self)intersecting curves in the plane so that a Gauss paragraph of this set of curves equals the original set of words. The same problem was recently studied by Schellhorn [12], who extended virtual strings introduced by Turaev [14] from single close curve S1 to sets of such curves and used them to characterize realizable Gauss paragraphs with a conjunction of seven technical conditions. In what follows, we give an elementary characterization that reduces the problem of realizability of a set of words to the problem of realizability of a single specific word obtainable from the set in linear time, avoiding the use of virtual strings. Besides showing that the problem of recognizing Gauss paragraphs is equivalent to recognizing Gauss words, the main improvement over Shcellhorn's characterization is the added algorithmic transparency.
2 Characterization of Gauss paragraphs
We first summarize some of the used notation. A double-occurrence word over an alphabet E is a word in which every letter of E appears exactly twice. The double-occurrence words that are Gauss words of some self-intersecting curve have been characterized by Rosenstiehl [10,11] and de Fraysseix and de Mendez [3]. Rosenstiehl proved the following algebraic characterization of Gauss words.
Theorem 2.1. [10, Theorem 2'] A double-occurrence word W on a finite set E of letters is a Gauss word if, and only if,
1.	any letter of W has an even number of interlaced letters;
2.	any non-interlaced pair of letters has an even number of common interlaced letters;
3.	the interlaced pairs having an even number of common interlaced letters form a separating set S, i.e. there exists E' C E, such that any pair of S has a letter of E' and a letter of E \ E'.
The last condition of the theorem suggests it has a natural graph-theoretic formulation. We state it in terms of the interlace-graph GW of a Gauss word W over the alphabet E, defined so that the letters of E are the vertex set, V(GW) = E, and two vertices u,v e E are adjacent in GW, uv e E(GW), if and only if they interlace in W. A cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition.
D. Archdeacon, D. Bokal and T. Gologranc: A characterization of plane Gauss paragraphs 33
Using these concepts, Theorem 2.1 can be stated as the following:
Theorem 2.2 ([3]). Let W be a double-occurrence word over a finite alphabet E and let GW be its interlace-graph. Then W is a Gauss word if and only if
1.	each component of GW is Eulerian;
2.	if u and v are two nonadjacent vertices of GW, then they have an even number of common neighbors;
3.	the set {e = uv | u, v have an even number of common neighbors} is a cut-set in GW.
When studying sets of curves, a crossing may appear on different curves, so we need to relax the condition of double-occurrence. We define a semi-double-occurence word over an alphabet E to be a word, in which every letter of E appears at most twice. Then, a double-occurence k-paragraph1 (shortly, k-DOP) over an alphabet E is a set of k semi-double-occurence words over E, such that each letter appears precisely twice in the union of all words of the paragraph. Further, a mixed crossing of a set of (self)intersecting curves in the plane is a crossing of two different curves, i.e. not a self-crossing of some word. Correspondingly, a mixed letter of a k-DOP P is a letter that appears in two different words of P. With M (P) or just M, when the paragraph is clear from the context, we will denote the mixed letters of P.
Note that, in contrast to some knot-theoretic bibliography [1], our definition follows the original definition of Gauss, which does not encode over- or under-pass information that is required for knot-theoretic investigation. For us, the curves are embedded in the plane and each crossing is either a self-crossing of some curve, appearing twice in the same word, or is a crossing of two curves, appearing once in each corresponding word.
Finally, for a k-DOP P = (wi,..., wk), we define its intersection graph G(P) as the graph whose vertices are words of P, V(G(P)) = P, in which two vertices are adjacent, iff the corresponding words share a letter of E.
Let P be k-DOP that contains x e M. Then we will simplify notation and write P =
(xwi, XW2, . . . , Wfc ).
Lemma 2.3. Let P = (xw1, xw2,..., wk) be a k-DOP and let x e M be a selected letter appearing in the first two words. Then P is a Gauss paragraph, if and only if the (k — l)-DOP Px = (xx'w1xx'w2, w3,..., wk) is a Gauss paragraph.
Proof. Suppose first that P is a Gauss paragraph. Let n be a drawing that realizes P. In n, replace x in its small neighborhood by a digon xx' with incoming edges adjacent to x and outgoing to x' (see Figure 1). The resulting embedding is an embedding of (k — 1)-DOP Px, showing that Px is a Gauss paragraph.
For the converse, suppose that Px is a Gauss paragraph, realized in n. We will first prove that xx' is not a cut. Indeed, if xx' is a cut, then x and x' are not interlaced in n, a contradiction. Since x and x' induce a cycle and do not induce a cut, one of the faces of this cycle is empty and the other contains the full embedding. This implies that the out-edges and the in-edges come consecutive in the vertex rotation around the empty face. By
1 As pointed out by one of the referees, a more natural name for this concept would be a sentence, as sentence is the next grammatical structure composed of words. Indeed we used double-occurrence sentence and Gauss sentence until a more thorough search through the bibliography [1] revealed that it was studied under the name Gauss paragraph.
34
Ars Math. Contemp. 12 (2017) 111-126
contracting the empty face, x and x' become a single point. By rerouting the curves so that x is a crossing, we get a realization of P.	□
Figure 1: Replacing x with digon xx' or vice versa.
We say that Px from Theorem 2.3 is an x-reduction of P. With a sequence of reductions, we would like to obtain a single word. Let x G w1 n w2. Since the letters appearing only in wi and w2, after x-reduction appear in a common word, at most (k — 1) reductions reduce a Gauss paragraph to a single word, to which we can apply Theorem 2.2.
Let P be a k-DOP and G(P) the intersection graph of semi-double-occurence words of P; its vertices are words and two words are adjacent if they have at least one letter in common. Let T be a tree in G(P) and w1,...,wt the vertices of T, such that wj has at most one neighbor in {wi+1,..., wt} and the connecting edge results from letter m, G M. Let w1 = w1. We define recursively wl+1 = mimiwi mim'iwi+1, i = 1,... ,t — 1. The T-reduction of P is PT = (wt,wt+1,...,wfc). By induction, using the previous lemma as induction step, we get the following result:
Theorem 2.4. Let P = (w1,..., wk) be a k-DOP and let T be a tree in G(P) on t vertices v1,... ,vt, such that v has at most one neighbour in {vi+1,... vt}. Then P is a Gauss paragraph, if and only if PT is a Gauss paragraph.
Applying this corollary to a spanning tree of G, we get the following characterization of k-DOPs that are Gauss paragraphs:
Corollary 2.5. Let P = (w1,.. .,wk). Let T be a spanning tree in G(P), and let W be the only word of PT. Then P is a Gauss paragraph, iff W is a Gauss word, i.e. iff GW satisfies the conditions of Theorem 2.2.
It is clear that this corollary implies existence of a polynomial algorithm for determining whether a k-DOP is a Gauss paragraph, and thus satisfies Edmonds' criterion for a good characterization [4]: if A is the adjacency matrix of a graph G, then A2 counts the number of length-two walks between any pair of vertices, i.e., the number of common neighbors, the crucial information required for verifying conditions of Theorem 2.2. The matrix A2 can be computed in O(|V(G)|w) time, with w < 2.376, using fast matrix multiplication. This yields the dominating time-complexity term O(|£|w) of the k-DOP realizability verifying algorithm, as running time of the algorithm is dominated by the requirement to count the common neighbors of any pair of vertices of GW, either adjacent or not. There are |E| + k vertices of GW, but the vertices x and x' have the same set of neighbors and are adjacent, hence with some preprocessing it suffices to check only a matrix of size |E|.
D. Archdeacon, D. Bokal and T. Gologranc: A characterization of plane Gauss paragraphs 35
Note that the best known time complexity of exact counting of all triangles in a general graph with n vertices (which is equivalent to counting the common neighbors of just the adjacent pairs of graph's vertices) is O(nu) [7], which indicates that the time complexity of checking realizability of a given k-DOW using conditions of Theorem 2.2 can hardly be improved, unless some detailed properties of the graph GW are exploited in counting the common neighbors. However, as constructing the graph G(P) can be done in time O(|E|), its spanning tree T found in O(k), and the T-reduction of P found in O(k + |E|), then any improvement in checking realizability of a double-occurring word immediately translates into an improvement of checking realizability of k-DOP.
Acknowledgements
This research was supported by the internationalisation of Slovene higher education within the framework of the Operational Programme for Human Resources Development 20072013 and by the Slovenian Research Agency project L7-5459.
References
[1]	J. S. Carter, Classifying immersed curves, Proc. Amer. Math. Soc. 111 (1991), 281-287, doi: 10.2307/2047890, http://dx.doi.org/10.2307/2047890.
[2]	B. Courcelle, The common structure of the curves having a same Gauss word, in: Automata, universality, computation, Springer, Cham, volume 12 of Emerg. Complex. Com-put., pp. 1-37, 2015, doi:10.1007/978-3-319-09039-9, http://dx.doi.org/10.10 07/ 978-3-319-09039-9_1.
[3]	H. de Fraysseix and P. Ossona de Mendez, On a characterization of Gauss codes, Discrete Comput. Geom. 22 (1999), 287-295, doi:10.1007/PL00009461, http://dx.doi.org/ 10.1007/PL00009461.
[4]	J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 67-72.
[5]	C. F. Gauss, Werke, Georg Olms Verlag, Hildesheim-New York, 1976, erganzungsreihe. IV. Briefwechsel C. F. Gauss-H. W. M. Olbers, I, Nachdruck der 1900 Auflage, herausgegeben von C. Schilling.
[6]	B. Grunbaum, Arrangements and spreads, American Mathematical Society Providence, R.I., 1972, conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10.
[7]	M. Latapy, Main-memory triangle computations for very large (sparse (power-law)) graphs, Theoret. Comput. Sci. 407 (2008), 458-473, doi:10.1016/j.tcs.2008.07.017, http://dx. doi.org/10.1016/j.tcs.2008.07.017.
[8]	L. Lovasz and M. L. Marx, A forbidden substructure characterization of Gauss codes, Bull. Amer. Math. Soc. 82 (1976), 121-122.
[9]	M. L. Marx, The Gauss realizability problem, Proc. Amer. Math. Soc. 22 (1969), 610-613.
[10]	P. Rosenstiehl, A new proof of the Gauss interlace conjecture, Adv. in Appl. Math. 23 (1999), 3-13, doi:10.1006/aama.1999.0643, http://dx.doi.org/10.10 0 6/aama.
1999.0643.
[11]	P. Rosenstiehl and R. C. Read, On the principal edge tripartition of a graph, Ann. Discrete Math. 3 (1978), 195-226, advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977).
36
Ars Math. Contemp. 12 (2017) 111-126
[12]	W. Schellhorn, Virtual strings for closed curves with multiple components and filamentations for virtual links, 2015, arXiv:math/0412023.
[13]	L. B. Treybig, A characterization of the double point structure of the projection of a polygonal knot in regular position, Trans. Amer. Math. Soc. 130 (1968), 223-247.
[14]	V. Turaev, Virtual strings, Ann. Inst. Fourier (Grenoble) 54 (2004), 2455-2525 (2005), http: //aif.cedram.org/item?id=AIF_20 04_5 4_7_2 455_0.