%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[a5]{llncs}
\begin{document}
\def\C{{\cal C}}
\def\CC{{\cal C}^\perp}
\def\E{\bbbz_2^E}
\def\dsw{\mathbin{\circ{\mkern-6mu}\circ}}
\def\lacute{\mathopen{<}}
\def\racute{\mathclose{>}}
\def\typeset{}
\title{A Short Proof of a Gauss Problem
 \author{H. de Fraysseix and P. Ossona de Mendez}
\thanks{This work was partially supported by the {\bf Esprit LTR Project no 
20244-ALCOM~IT}.}}
\institute{CNRS UMR 0017, EHESS, 54 Boulevard Raspail, 75006, Paris, France.}
\maketitle
\begin{abstract}
The traversal of a self crossing closed plane curve, with points
of multiplicity at most two, defines a double occurrence sequence.

C.F. Gauss conjectured \cite{Gauss3} that such
sequences could be
charactacterized by their interlacement properties.
The conjecture was by
P. Rosenstiehl in 1976 \cite{GaussCR}.
We shall give here a simple self contained proof of his characterization.
This new proof relies on the D-switch operation.
\end{abstract}

\section{Introduction}
We first recall and introduce some definitions and notations
concerning geometric properties of closed plane curves.
For related topics, we refer the reader to the bibliography.
\nocite{ Bouchet, Dehn, Fleischner, Francis, Gauss3, Gauss, Kotzig, Lovasz, Marx, Nagy, 
GaussPR, GaussCR, 
GaussPRRT, GaussPRCNRS, Shank, TutteCross, Tri, FutureGauss}
P. Rosenstiehl exposed recently a new proof of this theorem, based on patches, that will soon 
be published.

A {\em parameterized curve} $C$ is a continuous mapping 
$C:[0,1]\rightarrow\bbbr^2$, such that $C(0)=C(1)$ and such that
the {\em underlying curve}
$C([0,1])$ of $C$ has a finite number of multiple points, 
which all have multiplicity two.
The set of the points of multiplicity two is denoted $P(C)$. To any point $p\in P(C)$,
we associate $t_p'$ and $t_p''$, such that $t_p'<t_p''$ and $C(t_p')=C(t_p'')=p$.
A point $p\in P(C)$ is a {\em crossing point} if any local deformation of $C$ in a
neighborhood of $t_p'$ preserves the existence of a double point. Otherwise,
$p$ is a {\em touching point}. 
A {\em touch curve} (resp. a {\em cross curve})
is a parameterized curve with touching points (resp. crossing points)
only.

There are two different types of touching points, depending on the local
behavior of the parameterized curve~:
\begin{center}
\unitlength 1mm
\begin{picture}(80,20)(0,0)
%
\thicklines
\put(0,0){\vector(1,0){5}}
\put(0,10){\line(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,10){\vector(-1,0){1}}
\put(6,5){\oval(14,10)[r]}
\thinlines
\put(20,5){\oval(14,10)[l]}
\put(20,0){\vector(1,0){1}}
\put(26,0){\line(-1,0){5}}
\put(20,10){\line(1,0){1}}
\put(26,10){\vector(-1,0){5}}
\put(13,5){\circle*{1.5}}
%
\put(7,15){\makebox{Type 1}}
%
%
\put(50,0){
\thicklines
\put(0,0){\vector(1,0){5}}
\put(0,10){\line(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,10){\vector(-1,0){1}}
\put(6,5){\oval(14,10)[r]}
\thinlines
\put(20,5){\oval(14,10)[l]}
\put(20,0){\line(1,0){1}}
\put(26,0){\vector(-1,0){5}}
\put(20,10){\vector(1,0){1}}
\put(26,10){\line(-1,0){5}}
\put(13,5){\circle*{1.5}}
\put(7,15){\makebox{Type 2}}
}
%
\end{picture}
\end{center}
Remark that if $C$ is a touch curve, then all its touch points are of type $1$.

The sequence of the points of $P(C)$ encountered while the parameter $t$ goes from
$0$ to $1$ (excluded) is the {\em traversal sequence} of $C$ and is denoted by $S(C)$.

In the following, {\em sequences} are understood to have two occurrences of each symbol and
to be defined up to reversal and cyclic permutation. Given a sequence $S$,
two symbols $p,q$ are {\em interlaced} in $S$ if exactly one occurrence of $q$
appears in $S$ between the two occurrences of $p$.
We shall denote by $\Lambda(S)$ the {\em interlacement graph}
of $S$ defined by the interlacement relation in $S$.

A sequence $S$ is {\em realized} by a parameterized curve $C$ if
$S$ is the traversal sequence of $C$. A sequence is {\em touch realizable}
(resp. {\em cross realizable}) if it can be realized by a touch curve
(resp. a cross curve).             
\section{switches and D-switches}
Let us introduce the {\em switch} operation \cite{Dehn,Kotzig}~:
Given a point $p$ of $P(C)$, the curve $C'=C\circ p$ is defined by
$C'(t)=C(t)$ if $t\not\in[t_p',t_p'']$ and $C'(t)=C(t_p'+t_p''-t)$ if 
$t\in[t_p',t_p'']$. This curves as the same touching and crossing points as $C$,
with the possible exception of $p$. The traversal sequence of $C'$ is obtained
from the one of $C$ by inverting the order of the points encountered between the two
occurrences of $p$. We shall say that the points that are interlaced with $p$
have been {\em inverted}.
The switch operation on $S$ will be denoted by $S\circ p$, so that~:
$S(C\circ p)=S(C)\circ p$.
Let us remark that these switch operations are involutions~:
$C\circ p\circ p=C$ and $S\circ p\circ p = S$.
\begin{remark}
A $switch$ transforms any point of a parameterized point the following way~:
\begin{itemize}
\item touching point of type 1 $\leftrightarrow$ crossing point,
\item touching point of type 2 $\leftrightarrow$ touching point of type 2.
\end{itemize}
\end{remark}
\begin{center}
\unitlength 1mm
\begin{picture}(80,25)(0,0)
%
\put(0,15){
\thicklines
\put(0,0){\vector(1,0){5}}
\put(0,10){\line(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,10){\vector(-1,0){1}}
\put(6,5){\oval(14,10)[r]}
\thinlines
\put(20,5){\oval(14,10)[l]}
\put(20,0){\vector(1,0){1}}
\put(26,0){\line(-1,0){5}}
\put(20,10){\line(1,0){1}}
\put(26,10){\vector(-1,0){5}}
\put(13,5){\circle*{1.5}}
}
%
\put(35,20){\makebox{$\longleftrightarrow$}}
%
\put(50,15){
\thicklines
\put(0,0){\vector(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,5){\oval(14,10)[rb]}
\thinlines
\put(0,10){\vector(1,0){5}}
\put(6,10){\line(-1,0){1}}
\put(6,5){\oval(14,10)[rt]}
\thinlines
\put(20,5){\oval(14,10)[lb]}
\put(20,0){\vector(1,0){1}}
\put(26,0){\line(-1,0){5}}
\thicklines
\put(20,5){\oval(14,10)[lt]}
\put(20,10){\vector(1,0){1}}
\put(26,10){\line(-1,0){5}}
\put(13,5){\circle*{1.5}}
}
%
%
\put(0,0){
\thicklines
\put(0,0){\vector(1,0){5}}
\put(0,10){\line(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,10){\vector(-1,0){1}}
\put(6,5){\oval(14,10)[r]}
\thinlines
\put(20,5){\oval(14,10)[l]}
\put(20,0){\line(1,0){1}}
\put(26,0){\vector(-1,0){5}}
\put(20,10){\vector(1,0){1}}
\put(26,10){\line(-1,0){5}}
\put(13,5){\circle*{1.5}}
}
%
\put(35,5){\makebox{$\longleftrightarrow$}}
%
\put(50,0){
\thicklines
\put(0,0){\vector(1,0){5}}
\put(5,0){\line(1,0){1}}
\put(6,5){\oval(14,10)[rb]}
\thinlines
\put(0,10){\vector(1,0){5}}
\put(6,10){\line(-1,0){1}}
\put(6,5){\oval(14,10)[rt]}
\thicklines
\put(20,5){\oval(14,10)[lb]}
\put(20,0){\vector(1,0){1}}
\put(26,0){\line(-1,0){5}}
\thinlines
\put(20,5){\oval(14,10)[lt]}
\put(20,10){\vector(1,0){1}}
\put(26,10){\line(-1,0){5}}
\put(13,5){\circle*{1.5}}
}
\end{picture}
\end{center}
Remark that
if $q$ is a touching point of $C$ different from $p$, then $q$ is a touching point
with a type different in $C$ and $C\circ p$ if and only $p$ and $q$ are interlaced.

The switch in a sequence $S$ of a point $p$ induces a {\em local complementation} of $p$
in the interlacement graph $\Lambda(S)$~: 
two points $a,b$ are adjacent in $\Lambda(S\circ p)$ if and only if
\begin{itemize}
\item $a$ or $b$ is not adjacent to $p$ in $\Lambda(S)$ and $(a,b)$ is an edge
of $\Lambda(S)$, or
\item $a$ and $b$ are both adjacent to $p$ in $\Lambda(S)$ and $(a,b)$ is not an edge
of $\Lambda(S)$.
\end{itemize}
For sake of simplicity, the local complementation of $p$ in $\Lambda(S)$ will be denoted
by $\Lambda(S)\circ p$, so that $\Lambda(S\circ p)=\Lambda(S)\circ p$.

Let $S$ be a sequence, a {\em D-switch} consists in a switching at $p$ and in the
adding of two occurences of a symbol $p'$ (called {\em twin} of $p$),
one just after the first occurrence of $p$ and one just before the second occurrence
of $p$.
$$S=(\alpha p \beta p \gamma)\mapsto S\dsw p = (\alpha p p' \beta^{-1} p' p \gamma)$$

A D-switch of $p$ in $S$ corresponds in $\Lambda(S)$ to a local complementation
of $p$ and the adding of a new vertex having the same neighbors as $p$. It will be
denoted by the same symbol, so that $\Lambda(S)\dsw p = \Lambda(S\dsw p)$.

Remark that the sequence obtained from $S\dsw p\dsw p$ by deleting the two
twins of $p$ is equal to $S$.
\section{On realizable sequences}
We first state two propositions proved by Dehn, which follow
from the remarks of the preceding sections.
\begin{proposition}
Consider a cross curve $C$ and
any given order on the points. Then, the parameterized curve
$C\circ p_1\circ\dots\circ p_n$ obtained from $C$ by switching successively the $p_i$
is a touch curve.
\qed\end{proposition}

Let $S$ be a sequence
and $S'=S\circ p_1\circ\dots\circ p_n$ the sequence
obtained by switching successively the symbols of $S$.
The sequence $S'$ may be touch realizable even if $S$ is not cross realizable
(e.g. the sequence $S=(a b a b)$).

Assume $S'$ is realized by a touch curve $C$ and that the transformation
of each touching point of $C$ into a crossing point gives rise to one connected curve with
traversal sequence $S''$ (with the same interlacement graph as $S$).
We are not assured that $S$ and $S''$ are equal.
In fact, we are not even
assured that a proper order of switching allows to obtain $S'$ from $S''$.

Moreover, a cross-realizable sequence does not determine the cross curve itself
up to an homeomorphism and different cross-realizable sequences may have the
same interlacement graph (e.g. the sequences $(a b c a e f d c b e f d)$ and
$(a c b a e f d b c e f d)$).

The figure bellow shows how a touch curve may be transformed into a bipartite
chord diagram with the same interlacement (and conversely). 
\begin{center}
\unitlength 2pt
\begin{picture}(155,80)(0,-5)
\put(5,5){\oval(10,10)[bl]}
\put(5,0){\line(1,0){5}}
\put(15,0){\vector(-1,0){5}}
\put(15,5){\oval(10,10)[r]}
\put(10,10){\vector(1,0){5}}
\put(10,15){\oval(10,10)[bl]}
\put(5,15){\line(0,1){5}}
\put(5,25){\vector(0,-1){5}}
\put(10,25){\oval(10,10)[lt]}
\put(0,5){\vector(0,1){15}}
\put(15,30){\vector(-1,0){5}}
\put(15,32){\oval(4,4)[br]}
\put(20,32){\oval(6,6)[t]}
\put(25,32){\oval(4,4)[bl]}
\put(30,30){\vector(-1,0){5}}
\put(30,25){\oval(10,10)[tr]}
\put(35,15){\vector(0,1){5}}
\put(35,25){\line(0,-1){5}}
\put(30,15){\oval(10,10)[br]}
\put(25,10){\vector(1,0){5}}
\put(25,5){\oval(10,10)[l]}
\put(30,0){\vector(-1,0){5}}
\put(30,0){\line(1,0){5}}
\put(35,5){\oval(10,10)[br]}
\put(40,5){\line(0,1){15}}
\put(0,20){\vector(0,1){30}}
\put(0,50){\line(0,1){15}}
\put(5,65){\oval(10,10)[tl]}
\put(5,70){\vector(1,0){10}}
\put(15,65){\oval(10,10)[r]}
\put(15,60){\vector(-1,0){5}}
\put(10,55){\oval(10,10)[tl]}
\put(5,55){\vector(0,-1){5}}
\put(5,50){\line(0,-1){5}}
\put(10,45){\oval(10,10)[bl]}
\put(10,40){\vector(1,0){5}}
\put(15,38){\oval(4,4)[tr]}
\put(20,38){\oval(6,6)[b]}
\put(25,38){\oval(4,4)[tl]}
\put(25,40){\vector(1,0){5}}
\put(30,45){\oval(10,10)[br]}
\put(35,45){\vector(0,1){5}}
\put(35,50){\line(0,1){5}}
\put(30,55){\oval(10,10)[tr]}
\put(30,60){\vector(-1,0){5}}
\put(25,65){\oval(10,10)[l]}
\put(25,70){\vector(1,0){5}}
\put(30,70){\line(1,0){5}}
\put(35,65){\oval(10,10)[tr]}
\put(40,65){\vector(0,-1){15}}
\put(40,50){\vector(0,-1){30}}
\put(20,5){\circle*{1.5}}
\put(14,4){\makebox(5,5)[rb]{c}}
\put(20,65){\circle*{1.5}}
\put(14,64){\makebox(5,5)[rb]{a}}
\put(20,35){\circle*{1.5}}
\put(17,36){\makebox(5,5)[rb]{b}}
%
\thicklines
\put(50,35){\vector(1,0){5}}
\put(50,35){\vector(-1,0){5}}
\thinlines
%
\put(60,0){
\put(5,5){\oval(10,10)[bl]}
\put(5,0){\line(1,0){5}}
\put(15,0){\vector(-1,0){5}}
\put(15,5){\oval(10,10)[r]}
\put(10,10){\vector(1,0){5}}
\put(10,15){\oval(10,10)[bl]}
\put(5,15){\line(0,1){5}}
\put(5,25){\vector(0,-1){5}}
\put(10,25){\oval(10,10)[lt]}
\put(0,5){\vector(0,1){15}}
\put(15,30){\vector(-1,0){5}}
\put(15,31){\oval(2,2)[br]}
\put(25,31){\oval(18,2)[t]}
\put(35,31){\oval(2,2)[bl]}
\put(40,30){\vector(-1,0){5}}
\put(40,25){\oval(10,10)[tr]}
\put(45,15){\vector(0,1){5}}
\put(45,25){\line(0,-1){5}}
\put(40,15){\oval(10,10)[br]}
\put(35,10){\vector(1,0){5}}
\put(35,5){\oval(10,10)[l]}
\put(40,0){\vector(-1,0){5}}
\put(40,0){\line(1,0){5}}
\put(45,5){\oval(10,10)[br]}
\put(50,5){\line(0,1){15}}
\put(0,20){\vector(0,1){30}}
\put(0,50){\line(0,1){15}}
\put(5,65){\oval(10,10)[tl]}
\put(5,70){\vector(1,0){10}}
\put(15,65){\oval(10,10)[r]}
\put(15,60){\vector(-1,0){5}}
\put(10,55){\oval(10,10)[tl]}
\put(5,55){\vector(0,-1){5}}
\put(5,50){\line(0,-1){5}}
\put(10,45){\oval(10,10)[bl]}
\put(10,40){\vector(1,0){5}}
\put(15,39){\oval(2,2)[tr]}
\put(25,39){\oval(18,2)[b]}
\put(35,39){\oval(2,2)[tl]}
\put(35,40){\vector(1,0){5}}
\put(40,45){\oval(10,10)[br]}
\put(45,45){\vector(0,1){5}}
\put(45,50){\line(0,1){5}}
\put(40,55){\oval(10,10)[tr]}
\put(40,60){\vector(-1,0){5}}
\put(35,65){\oval(10,10)[l]}
\put(35,70){\vector(1,0){5}}
\put(40,70){\line(1,0){5}}
\put(45,65){\oval(10,10)[tr]}
\put(50,65){\vector(0,-1){15}}
\put(50,50){\vector(0,-1){30}}
\thicklines
\put(20,5){\line(1,0){10}}
\put(20,65){\line(1,0){10}}
\put(25,32){\line(0,1){6}}
\put(20,5){\circle*{1.5}}
\put(14,4){\makebox(5,5)[rb]{c}}
\put(30,5){\circle*{1.5}}
\put(32,4){\makebox(5,5)[lb]{c}}
\put(20,65){\circle*{1.5}}
\put(14,64){\makebox(5,5)[rb]{a}}
\put(30,65){\circle*{1.5}}
\put(32,64){\makebox(5,5)[lb]{a}}
\put(25,32){\circle*{1.5}}
\put(22,26){\makebox(5,5)[rt]{b}}
\put(25,38){\circle*{1.5}}
\put(22,39){\makebox(5,5)[rb]{b}}
\thinlines
}
\thicklines
\put(120,55){\vector(1,0){5}}
\put(120,55){\vector(-1,0){5}}
\thinlines
%
\put(145,55){
\put(0,0){\circle{20}}
\thicklines
\put(-8,10){\oval(4,8)[bl]}
\put(0,10){\oval(20,10)[t]}
\put(8,10){\oval(4,8)[br]}
\put(-8,-10){\oval(4,8)[tl]}
\put(0,-10){\oval(20,10)[b]}
\put(8,-10){\oval(4,8)[tr]}
\thinlines
\put(0,-10){\line(0,1){20}}
\put(-8,6){\circle*{1.5}}
\put(-15,4){\makebox(5,5)[rb]{a}}
\put(8,6){\circle*{1.5}}
\put(10,4){\makebox(5,5)[lb]{a}}
\put(-8,-6){\circle*{1.5}}
\put(-15,-6){\makebox(5,5)[rb]{c}}
\put(8,-6){\circle*{1.5}}
\put(10,-6){\makebox(5,5)[lb]{c}}
\put(0,10){\circle*{1.5}}
\put(-3,11){\makebox(5,5)[rb]{b}}
\put(0,-10){\circle*{1.5}}
\put(-3,-16){\makebox(5,5)[rt]{b}}
}
\thicklines
\put(145,32){\vector(0,-1){5}}
\put(145,32){\vector(0,1){5}}
\thinlines
\put(145,10){
\put(0,0){\circle{20}}
\thicklines
\put(-8,6){\line(1,0){16}}
\put(-8,-6){\line(1,0){16}}
\thinlines
\put(0,-10){\line(0,1){20}}
\put(-8,6){\circle*{1.5}}
\put(-15,5){\makebox(5,5)[rb]{a}}
\put(8,6){\circle*{1.5}}
\put(10,5){\makebox(5,5)[lb]{a}}
\put(-8,-6){\circle*{1.5}}
\put(-15,-7){\makebox(5,5)[rb]{c}}
\put(8,-6){\circle*{1.5}}
\put(10,-7){\makebox(5,5)[lb]{c}}
\put(0,10){\circle*{1.5}}
\put(-3,11){\makebox(5,5)[rb]{b}}
\put(0,-10){\circle*{1.5}}
\put(-3,-16){\makebox(5,5)[rt]{b}}
}
\end{picture}
\end{center}
Hence, we have~:
\begin{proposition}
A sequence $S$ is touch realizable if and only if its interlacement graph $\Lambda(S)$
is bipartite.
\qed\end{proposition}

\begin{theorem}
\label{th_dsw}
Let $S$ be a sequence $S$, with any given order on the symbols. Then,
$S$ is cross realizable if and only if the sequence
$S_n=S\dsw p_1\dsw\dots\dsw p_n$ obtained by successively D-switching the $p_i$
has a bipartite interlacement graph.
\end{theorem}
\begin{proof}
\begin{itemize}
\item Assume $S$ is realized by a cross curve $C$.
As a D-switch of a crossing point of a parametrized curve gives
rise to two touching points (that will never become crossing points again),
the curve $C$ is iteratively transformed into a touch curve $C_n$.
The traversal sequence $S_n$ of $C_n$ has hence a bipartite interlacement
graph.

\item Conversely, assume that $S_n$ has a bipartite interlacement graph.

Let $S_i=S \dsw p_1\dsw\dots\dsw p_i$ denote the sequence obtained after the first $i$ 
D-switches, we shall inductively construct (for $i$ going from $n$ to $0$)
a parameterized curve $C_i$, that realizes $S_i$, and such that
the crossings of $C_i$ are the $p_j$, with $j>i$.
Then, the parameterized curve $C_0$ will be a cross curve realizing $S$.

As $\Lambda(S_n)$ is bipartite,
there exists a touching curve $C_n$ whose traversal sequence is $S_n$.

If $p_i$ is of type 1,
the suppression of $p_i'$ and the a switch at $p_i$ transforms $p_i$ into
a crossing point and gives rise to $C_{i-1}$, having $p_i,\dots,p_n$ as crossing points
and $S_{i-1}$ as traversal sequence.

So, the proof will be complete if we prove that $p_i$ is of type 1 in $C_i$,
that is that $p_i$ has been inverted an even number of times during
the D-switch at $p_i,\dots,p_n$~:
The symbol $p_i$ and its twin $p_i'$ are not interlaced in $S_i$,
they are alternatively interlaced and non-interlaced
after each further inversion and,
if $p_i$ has been last inverted by a switch at $p_j$, 
$p_i$ (resp. $p_i'$) and $p_j$ are interlaced in $S_n$. 
As $\Lambda(S_n)$ is bipartite,
$p_i$ and $p_i'$ are not interlaced in $S_n$ (else $p_i,p_i',p_j$ would define
a triangle of $\Lambda(S_n)$). Hence,
the symbol $p_i$ has been inverted
an even number of times.
\end{itemize}
\qed\end{proof}

Remark that a cross curve realizing the sequence $S$ could be geometrically derived
from a touch curve realizing the sequence $S'$ obtained from $S_n$ by suppressing
all twinned letters by transforming each touching point into a crossing point.

\section{Proof of Rosenstiehl's Theorem}

In the following, two vertices 
$u,v$ of a graph $G$ with a vertex bipartition ($A,B$) 
are said to satisfy the property $P$ if
they have an odd number of common neighbors if and only if
they are adjacent and belong to the same class ($A$ or $B$).

\begin{lemma}
\label{lemma_aller}
Let $G$ be a graph with a vertex bipartition $A,B$ 
and let $p$ be a vertex of $G$.
Let $G'=G\dsw p$ and let $A',B'$ be the vertex bipartition of $G'$ defined by~:
$A'=A+N(p), B'=B+N(p)$ and assigning $p'$ to the class of $p$.
If $G$ is eulerian
and any pair $u,v$ of vertices of $G$ satisfies $(P)$ (according to the
bipartition $A,B$), then
$G'$ is eulerian and
any pair $u,v$ of vertices of $G'$ satisfies $(P)$ (with respect to the bipartition
$A',B'$).
\end{lemma}
\begin{proof}
We have the following relationship between the neighborhood $N_{G'}$ in $G'$ and
the neighborhood $N_G$ in $G$~:
\begin{itemize}
\item $N_{G'}(u) = N_G(u)$, if $u$ is not adjacent to $p$ (in $G$ or equivalently in $G'$),
\item $N_{G'}(p') =N_{G'}(p) = N_G(p)$,
\item $N_{G'}(u) = N_G(u)+u+N_G(p)+p'$, if $u$ is adjacent to $p$.
\end{itemize}

In order to prove that $G'$ is eulerian, we only have to check that the neighbors
of $p$ have an even degree~:
the parity of $N_{G'}(u) = N_G(u)+u+N_G(p)+p'$ is the sum of the parities
of $N_G(u),\{u\},N_G(p)$ and $\{p\}$ and hence is even.

Now, we shall prove that any pair of vertices $u,v$ of $G'$ satisfies $(P)$, with respect to
the bipartition $A',B'$. If $u$ or $v$ is $p'$, we shall replace it by $p$ as
$p$ and $p'$ have the same neighbors, are not adjacent and belong to the same class 
($A',B'$).

If two vertices $u,v$ are not adjacent or equal to $p$,
 then their adjacencies, their class and their number of common neighbors are the same in $G$ 
and $G'$. Thus, the pair $u,v$ satisfies $(P)$.

If $u$ is adjacent to $p$ and $v$ is not adjacent or equal to $p$, then
\begin{eqnarray*}
\lacute N_{G'}(u),N_{G'}(v)\racute &=& \lacute N_G(u)+u+N_G(p)+p',N_G(v)\racute\\
&=&\lacute N_G(u),N_G(v)\racute +1
\end{eqnarray*}
As $u$ and $v$ belongs to the same class ($A',B'$) if
and only if they do not belong to the same class ($A,B$) and as they are adjacent, 
the pair $u,v$ satisfies $(P)$.

If $u$ and $v$ are both adjacent to $p$, then
\begin{eqnarray*}
\lacute N_{G'}(u),N_{G'}(v)\racute &=& \lacute N_G(u)+u+N_G(p)+p',N_G(u)+v+N_G(p)+p'\racute\\
&=&\lacute N_G(u),N_G(v)\racute +\lacute N(u),N(p)\racute+\lacute N(v),N(p)\racute+1
\end{eqnarray*}
As $u$ is adjacent to $p$, $\lacute N(u),N(p)\racute=1$ if and only if $u$ and $p$ belongs
to the same class ($A,B$).
So, $\lacute N(u),N(p)\racute+\lacute N(v),N(p)\racute+1 = 1$ if and only if $u$ and $v$
do not belongs to the same class ($A,B$). As $\lacute N_G(u),N_G(v)\racute=1$ if and only
if $u$ and $v$ are adjacent in $G$ and belongs to the same class ($A,B$),
$\lacute N_{G'}(u),N_{G'}(v)\racute = 1$ if and only if $u$ and $v$ are not adjacent in
$G$ and belong to the same class ($A,B$), that is, if and only if they are adjacent
in $G'$ and belong to the same class ($A',B'$). Thus, the pair $u,v$ satisfies $(P)$.
\qed\end{proof}
\begin{lemma}
\label{lemma_retour}
Let $G$ be a graph with a vertex bipartition $A,B$ 
and let $p$ be a vertex of $G$.
Let $G'=G\dsw p$ and let $A',B'$ be the vertex bipartition of $G'$ defined by~:
$A'=A+N(p), B'=B+N(p)$ and assigning $p'$ to the class of $p$.
If $G'$ is eulerian and
any pair $u,v$ of vertices of $G'$ satisfies $(P)$ (with respect to the bipartition
$A',B'$),then 
$G$ is eulerian and
any pair $u,v$ of vertices of $G$ satisfies $(P)$ (with respect to the
bipartition $A,B$).
\end{lemma}
\begin{proof}
By Lemma~\ref{lemma_aller}, $G''=G'\dsw p$ has the requested property and
this property is still satisfied when deleting the two twins of $p$.
\qed\end{proof}
\begin{theorem}[{\sc(Rosenstiehl)}]
A sequence $S$ is cross realizable if and only if its interlacement
graph $\Lambda(S)$ satisfy~:
\begin{itemize}
\item $\Lambda(S)$ is eulerian,
\item for any non-edge $(p,p')$ of $\Lambda(S)$, $N(p)\cap N(p')$ is even,
\item the set of the of the edges $(p,p')$ of $\Lambda(S)$ such that
$N(p)\cap N(p')$ is even is a cocycle of $\Lambda(S)$.
\end{itemize}
\end{theorem}
\begin{proof}
The theorem may be restated as follows~: 
A sequence $S$ is cross realizable if and only if its interlacement
graph $\Lambda(S)$ is eulerian and if there exists a bipartition $A,B$ of the vertex
set of $\Lambda(S)$ such that any pair $u,v$ of vertices of $\Lambda(S)$ satisfies $(P)$.

Consider any sequence $S_n=S\dsw p_1\dsw\dots\dsw p_n$ obtained by successively
D-switching the symbols of $S$.
According to Lemma~\ref{lemma_aller}, $\Lambda(S_n)$
is eulerian and has a bipartition $A',B'$ such that any pair of vertices of $\Lambda(S_n)$
satisfies $(P)$. As all the symbols have been twinned and as 
$p$ and its twin $p'$ have the same neighbors, any two vertices of $\Lambda(S_n)$ have
an even number of common vertices. According to property $(P)$, the graph
$\Lambda(S_n)$ is bipartite. Then, from Theorem~\ref{th_dsw}, $S$ is cross realizable.

Conversely, if $S$ is cross realizable, any sequence of D-switches
gives rise to a sequence $S'$ having a bipartite interlacement graph.
This graph is eulerian (due to the doubling of each symbol) and
a bipartition $A,B$ induced by a bicoloration, is such that each pair of vertices
satisfies $(P)$. The theorem then follows from Lemma~\ref{lemma_retour}.
\qed\end{proof}
\section{Matroidal Interpretation}
As we wanted to give a short self-contained proof, we did not introduce
the usual concepts of binary matroids. In such a context, a proof could
done, relying on the following properties~:
The graphs which satisfy the conditions given for $\Lambda(S)$ in Rosenstiehl's
characterization are exactly the principal interlacement graph of some binary matroid 
$M$ \cite{GaussPRCNRS}.
Any local complementation of the vertices of such a graph gives rise to
a bipartite graph, which is the fundamental interlacement graph of $M$ with respect
to some base $B$ of $M$ \cite{occu}.
The further condition that a principal interlacement graph is an interlacement graph 
(that is a circle graph) implies that the matroid $M$ is planar and then,
the principal interlacement graph corresponds to the interlacement of a left-right
path of a planar realization of $M$ \cite{occu}.
\begin{thebibliography}{10}

\bibitem{Bouchet}
A.~Bouchet.
\newblock Caract\'erisation des symboles crois\'es de genre nul.
\newblock {\em C.R. Acad. Sci.}, 274:724--727, 1972.
\newblock (Paris).

\bibitem{Gauss3}
H.~de~Fraysseix.
\newblock Sur la repr\'esentation d'une suite \`a triples et \`a doubles
  occurrences par la suite des points d'intersection d'une courbe ferm\'ee du
  plan.
\newblock In {\em Probl\`emes combinatoires et th\'eorie des graphes}, volume
  260 of {\em Colloques internationaux C.N.R.S.}, pages 161--165. C.N.R.S.,
  1976.

\bibitem{occu}
H.~de~Fraysseix.
\newblock Local complementation and interlacement graphs.
\newblock {\em Discrete Mathematics}, 33:29--35, 1981.

\bibitem{Dehn}
M.~Dehn.
\newblock \ \"Uber kombinatorische topologie.
\newblock {\em Acta Math.}, 67:123--168, 1936.
\newblock (Sweden).

\bibitem{Fleischner}
H.~Fleischner.
\newblock Cycle decompositions, 2-coverings, removable cycles, and the
  four-color-disease.
\newblock {\em Progress in Graph Theory}, pages 233--246, 1984.

\bibitem{Francis}
G.K. Francis.
\newblock Null genus realizability criterion for abstract intersection
  sequences.
\newblock {\em J. Combinatorial Theory}, 7:331--341, 1969.

\bibitem{Gauss}
C.F. Gauss.
\newblock {\em Werke}, pages 272 and 282--286.
\newblock Teubner Leipzig, 1900.

\bibitem{Kotzig}
A.~Kotzig.
\newblock Eulerian lines in finite 4-valent graphs and their transformations.
\newblock In {\em Proceedings of the Colloquium held at Tihany, Hungary}, pages
  219--230, 1969.

\bibitem{Lovasz}
L.~Lov\'asz and M.L. Marx.
\newblock A forbidden subgraph characterization of gauss codes.
\newblock {\em Bull. Am. Math. Soc.}, 82:121--122, 1976.

\bibitem{Marx}
M.L. Marx.
\newblock The gauss realizability problem.
\newblock {\em Trans Am. Math. Soc.}, 134:610--613, 1972.

\bibitem{Nagy}
J.V.Sz. Nagy.
\newblock \  \"Uber ein topologisches problem von gauss.
\newblock {\em Maht. Z.}, 26:579--592, 1927.
\newblock (Paris).

\bibitem{GaussPR}
R.C. Read and P.~Rosenstiehl.
\newblock On the gauss crossing problem.
\newblock In {\em Colloquia Mathematica Societatis J\'anos Bolyai}, pages
  843--875, 1976.
\newblock (Hungary).

\bibitem{Tri}
R.C. Read and P.~Rosenstiehl.
\newblock On the principal edge tripartition of a graph.
\newblock {\em Annals of Discrete Maths}, 3:195--226, 1978.

\bibitem{GaussPRCNRS}
P.~Rosenstiehl.
\newblock Les graphes d'entrelacement d'un graphe.
\newblock In {\em Probl\`emes combinatoires et th\'eorie des graphes}, volume
  260 of {\em Colloques internationaux C.N.R.S.}, pages 359--362. C.N.R.S.,
  1976.

\bibitem{GaussCR}
P.~Rosenstiehl.
\newblock Solution alg\'ebrique du probl\`eme de gauss sur la permutation des
  points d'intersection d'une ou plusieurs courbes ferm\'ees du plan.
\newblock {\em C.R. Acad. Sci.}, 283 (A):551--553, 1976.
\newblock (Paris).

\bibitem{FutureGauss}
P.~Rosenstiehl.
\newblock A geometric proof of a Gauss crossingg problem.
\newblock (to appear).

\bibitem{GaussPRRT}
P.~Rosenstiehl and R.E. Tarjan.
\newblock Gauss codes, planar hamiltonian graphs, and stack-sortable
  permutations.
\newblock {\em Jour. of Algorithms}, 5:375--390, 1984.

\bibitem{Shank}
H.~Shank.
\newblock The theory of left-right paths.
\newblock In {\em Combinatorial Math.}, volume III of {\em Lecture Notes in
  Math.}, pages 42--54. Springer, 1975.

\bibitem{TutteCross}
W.T. Tutte.
\newblock On unicursal paths in a network of degree 4.
\newblock {\em Amer. Math. Monthly}, 4:233--237, 1941.

\end{thebibliography}
\end{document}

