11institutetext: Université Côte d’Azur, CNRS, I3S, France

# Drawing non-planar graphs with rotation systems on the Klein bottle

François Doré  Enrico Formenti

###### Abstract

This paper provides a linear time algorithm in the number of edges that, given
a simple 3-connected non-planar graph $G$ with a Klein bottle rotation system,
outputs a straight line drawing of $G$ with no crossings on the flat Klein
bottle.

###### Keywords:

Straight-line drawing Rotation Systems Graph Embedding Non-orientable Surfaces

##  1 Introduction

Wagner [15] and Fáry [4], independently, proved that simple planar graphs
admit a straight-line representation on the plane. Mohar extended this result
to flat surfaces (2-polytopes where distinct sides are identified as one)
_i.e._ the cylinder, the Möbius band, the flat torus and the flat Klein bottle
[9]. However, even knowing that they exists, finding these representations is
not an easy task. Read proposed an algorithm to create a straight-line
representation of planar graphs given their rotation systems [12]. This
algorithm has then been adapted to the torus by Kocay et al. [7] but, to the
best of our knowledge, similar algorithms for non-orientable surfaces,
especially for the Klein bottle, have not been much studied.

Figure 1: Flat representation of the torus (left) and the Klein bottle
(right). Pairs of identified sides of the $[0,1]$ Square have here the same
number of markings on them but we will assume that these pairs always concern
two opposite sides

Although the torus and the Klein bottle seem similar at a first glance, there
are classes of graphs that can be embedded in the torus but not in the Klein
bottle and conversely. Riskin studied in detail the nonembeddability of
toroidal graphs on the Klein bottle and stated, in his conclusions, the
following conjecture [13]:

> Klein bottle polyhedral maps with four disjoint homotopic noncontractible
> circuits of the type that collapse the Klein bottle to the pinched torus are
> not toroidal.

The class of graphs described by Riskin’s conjecture is not the only one which
has a Klein bottle embedding but are not toroidal. Indeed, Figure 2 shows a
Klein-embeddable graph which does not satisfy the hypothesis of Riskin’s
conjecture but have a minor homeomorphic to a torus obstruction listed in the
database made by Myrvold and Woodcock [11].

08192103114125136147151415891011121367012345 Figure 2: An Klein embedding of a
square grid which is non-toroidal. The subgraph homeomorphic to a torus
obstruction is drawn by solid lines (left) and its embedding the plane
(right).

Indeed, the whole class of square grids of size $m\times n$ on the Klein
bottle where $m$ runs along the non-inverted side and $n$ runs along the
inverted side will be non-toroidal when $m\geq 2$ and $n\geq 8$ since they
contain the sub-grid of Figure 2.

These facts motivate the search for algorithms which given a rotation system
can build a straight-line drawing on the Klein bottle. This is the main matter
of the next sections. We stress that some of the algorithms are sufficiently
generic to be extendable to other surfaces.

##  2 Rotation systems and the Klein bottle

We will use the standard definitions and concepts from graph topology (for
more details see, for instance, the book of Mohar and Thomassen [10]). An
_embedding_ $\Lambda(G)$ of a graph $G=\left\langle V,E\right\rangle$ on a
surface $S$ is a representation of $G$ in which vertices are points on $S$ and
edges are simple curves homeomorphic to $[0,1]$ over $S$. This representation
is such that endpoints of a curve associated with an edge must coincide with
the endpoints of the edge, no curve representing an edge contains more than
two vertices and no two curves intersect at a common interior point. A _face_
of an embedding is a maximal contiguous region of $S-\Lambda(G)$. An embedding
is called _cellular_ if all its faces are homeorphic to disks. The _Euler’s
characteristic_ $\chi(\Lambda(G))$ of an embedding is equal to $|V|-|E|+|F|$,
where $F$ is the set of all the faces of $\Lambda(G)$.

It is well known that _orientable rotation systems_ of a graph $G$, or _pure_
rotation system, induce a unique embedding of $G$ on an orientable surface $S$
up to embedding equivalence, but this relation, is not necessarily the same in
the non-orientable case. Below, we define _general_ (or _non-orientable_)
rotation systems.

###### Definition 1

Let $G=\left\langle V,E\right\rangle$ be a graph, its _general rotation
system_ $\Pi(G)$ is the structure $\left\langle\pi,w\right\rangle$, where
$\pi=\left\\{\pi_{v}\mid v\in V\right\\}$ is the ordered adjacency of each
vertex, and $w=\left\\{w_{e}\mid e\in E\right\\}$ is the sign of each edge
(indicating if they are twisted or not).

From now on, we will consider that nodes labelled by integers in the set
$\left\\{1,\ldots,|V|\right\\}$. Thus, a node $u$ is lower than a node $v$ if
the same relation holds for their labels.

The rotation system $\Pi_{2}(G)$ is the _flip_ of $\Pi_{1}(G)$ iff the
adjacencies of all of its vertices are reversed _w.r.t._ those of
$\Pi_{1}(G)$. Two orientable rotation systems $\Pi_{1}(G)$ and $\Pi_{2}(G)$
are _equivalent_ if letting $\Pi$ be $\Pi_{1}(G)$ or its flip, for each node
of $\Pi$, there exists a cyclic permutation which transforms the ordered
adjacency into the one of $\Pi_{2}(G)$. In order to test the equivalence of
two orientable rotation systems $\Pi_{1}(G)$ and $\Pi_{2}(G)$, one can
consider the minimal cyclic permutation of the ordered adjacency of
$\Pi_{1}(G)$ and $\Pi_{2}(G)$ and then check the adjacency of the lowest node,
if the second node is greater than the last, we take the _flip_. With this
procedure, we can easily check if two rotation systems of one graph are
equivalent or not. However, with non-orentable rotation systems, this is no
longer sufficient.

01234$0$:$1$,$2$,$3$,$4$$1$:$0$,$4$,$3$,$2$$2$:$0$,$1$,$4^{-}$,$3$$3$:$0$,$2$,$1$,$4$$4$:$0$,$3$,$2^{-}$,$1$01234$0$:$1$,$2^{-}$,$3$,$4$$1$:$0$,$4$,$3$,$2^{-}$$2$:$0^{-}$,$3^{-}$,$4$,$1^{-}$$3$:$0$,$2^{-}$,$1$,$4$$4$:$0$,$3$,$2$,$1$
Figure 3: Two equivalent embeddings with different rotation systems. A minus
symbol at the exponent means that the edge is going through the inverted side
of the Klein bottle.

As shown in Figure 3, moving one node $v$ (the node $2$ in this case) through
an inverted side, implies changes on the rotation system (two changes in our
figure). First, the adjacency of $v$ is _flipped_ , meaning the order of its
adjacency is reversed. Second, all the edges incident to $v$ have their signs
changed. We call this operation _switching_ the vertex $v$.

Two rotations systems $\Pi_{1}(G)$ and $\Pi_{2}(G)$, such that $\Pi_{1}(G)$
can be obtained from $\Pi_{2}(G)$ by a sequence of flip/switch are said to be
_switch-equivalent_. We will denote this fact by $\Pi_{1}(G)\cong\Pi_{2}(G)$.
This means that we can freely and independently switch any vertex without
altering the rotation system. To have a rotation system independent of the
switches, we can switch the nodes $v$ whose $\pi_{v}$ needs to be flipped,
handle the changes for the edge signs accordingly and then consider the
minimal cyclic permutations as for the orientable case. An outline of this
formatting method is shown in Algorithm 1.

Algorithm 1 Format rotation system

1:$G=\left\langle V,E\right\rangle$,$\Pi(G)$

2:$\Pi(G)$

3:for $v\in V$ do

4: $u\leftarrow\min(\pi_{v})$

5: if $\pi_{v}.successor(u)>\pi_{v}.predecessor(u)$ then

6: for $e\in E(v)$ do

7: $w_{e}\leftarrow-w_{e}$

8: end for

9: $\pi_{v}\leftarrow flipped(\pi_{v})$

10: end if

11: $\pi_{v}\leftarrow rotated(\pi_{v})$

12:end for

The functions $\pi_{v}.successor(u)$ (resp. $\pi_{v}.predecessor(u)$) return
the node before (resp. after) $u$ in the ordered adjacency of $v$. The
functions $flipped(\pi_{v})$ and $rotated(\pi_{v})$ output respectively the
reverse and the minimal cycle permutation of $\pi_{v}$.

The rotation system formatting algorithm runs through all the vertices and
changes the sign of each edge at most twice, therefore its complexity is
$O(|V|+|E|)$.

This algorithm will be particularly useful when enumerating the embeddings
needed as a base for our drawing algorithm.

##  3 Enumerating the embeddings

In this section we are going to provide an enumeration algorithm for the
embeddings of a graph into a generic surface. We stress that enumeration is
not an easy task in general. Indeed, given a graph $G$ with $n$ nodes and $m$
edges, an upper bound for the number of labelled embeddings of $G$ is given by

$2^{m}\prod_{0<i\leq n}(d_{i}-1)!$

where $d_{i}$ is the degree of node $i$. Therefore, since we assumed $d_{i}>2$
the above bound is certainly larger than $2^{m+n}$ and hence for large values
of $m$ or $n$, labelled enumeration can be practically unfeasible. We
therefore prefer to enumerate the unlabelled embeddings up to isomorphism and
switch-equivalence. Some theoretical results exist in this domain, but no
tight bounds on the number of these embeddings nor a way to generate them
efficiently, to our knowledge, is known (see [2, 5] for further details).

To enumerate all possible unlabelled embeddings of a graph $G$ on the Klein
bottle, one can enumerate all the rotation systems of $K$, changing both
adjacencies and edge twists. For each possible rotation system $\Pi(G)$,
compute its genus (or Euler characteristic) with a face-walking algorithm to
keep only the ones with $\chi(\Pi(G))=0$, and store the minimal
(lexicographically ordered) formatted form among all the relabellisations of
$G$.

Although for small graphs, the complete enumeration can be done quite easily,
few optimizations can be done to minimize the number of times a canonical form
is generated.

Firstly, it is not mandatory to test all the possible relabellisations of
$\Pi(G)$ when computing its canonical form. One can simply test permutations
conserving the automorphism groups111See the Nauty library of McKay for
automorphism and isomorphism algorithms that have proved their worth and that
are usable in practice [8]..

A second step in this direction consists in exploiting a notion coming from
the domain of signed graphs, namely the _frustration_ of a graph.

###### Definition 2

Let $G=\left\langle V,E\right\rangle$ be a graph and $\Pi(G)$ an embedding of
$G$. The _frustration_ $f(\Pi(G))$ of $\Pi(G)$ is the minimum number of
twisted edges after any sequence of switches.

Figure 4: Three switch-equivalent signatures of $K_{5}$ (up to isomorphism)
having a frustration of 4. Solid (resp., dotted) lines represent positive
(resp., negative or twisted) edges. Curved arrows denote the possible switch-
transitions between signatures.

Now, we are going to define the frustration for standard (_i.e._ unsigned)
graphs.

###### Definition 3

Let $G=\left\langle V,E\right\rangle$ be a graph. The _frustration_ $f(G)$ of
$G$ is the maximum of the frustrations $f(\Pi(G))$ over all possible $\Pi(G)$
of $G$.

Having the notion of frustration in mind, there is no need to check for all
the configurations for edge signs. Indeed, it is well known that the
frustration of any graph is at most half the number of edges [1]. So only a
subset of all possible signatures is needed when enumerating the labelled
embeddings.

###### Theorem 3.1

Let $G=\left\langle V,E\right\rangle$ be a graph with $\Pi(G)$ its embedding
(potentially with twisted edges) and with $\chi(\Pi(G))=0$. If $f(\Pi(G))=0$,
then the corresponding embedding on the Klein bottle is not cellular.

###### Proof

Let $G$ be a graph satisfying the hypothesis. Assume $f(\Pi(G))=0$. Then,
there exists a way to move the nodes of $G$ on the Klein bottle in such a way
that there are no twisted edges anymore, _i.e._ we can produce an embedding
$\Pi^{\prime}(G)$ in which all the edges are either fully contained in
$[0,1]^{2}$ or passing through the non-inverted identified sides. Thus, there
is at least one face, the one containing the inverted side, which is not
homeomorphic to a disk.

Finally, the following theorem provides a criterion to exclude some rotation
systems which are, in practice, not embeddable in the Klein bottle.

###### Theorem 3.2

Let $G=\left\langle V,E\right\rangle$ be a non-planar graph with $\Pi(G)$. If
$\chi(\Pi(G))=0$ and $f(\Pi(G))=0$, then there is no embedding of $G$
corresponding to $\Pi(G)$ in the Klein bottle.

###### Proof

By Theorem 3.1, if $f(\Pi(G))=0$, there is a face homeomorphic to a cylinder.
By cutting through it, the supposed embedding of $G$ becomes a cylindrical
one. However, each cylindrical embedding is necessarily planar (by identifying
one of the two borders as one point) which is a contradiction.

Algorithm 2 Enumerating distinct Klein bottle embeddings

1:$G=\left\langle V,E\right\rangle$

2:$X_{\text{False}}\leftarrow set()$

3:$X_{\text{All}}\leftarrow set()$

4:for $edgeMask=0$ to $2^{|E|}-1$ do

5: for $(\sigma_{0},\ldots,\sigma_{|V|-1})\in\prod_{0<i\leq|V|}S_{d_{i}-1}$ do

6: $\Pi(G).clear()$

7: $sortedEdges\leftarrow sorted(E)$

8: for $i=0$ to $|E|-1$ do

9: $e\leftarrow sortedEgdes[i]$

10: $w_{e}\leftarrow 1|-(edgeMask>>i\&1)$

11: end for

12: for $v\in V$ do

13: $u_{min}\leftarrow min(V(v))$

14:
$\pi_{v}\leftarrow[u_{min}]+sorted(V(v)\backslash\left\\{u_{min}\right\\})^{\sigma_{v}}$

15: end for

16: if $\chi(\Pi(G))=0$ then

17: $\Pi\leftarrow min(\left\\{(\Pi(G)^{\sigma}).format()\mid\sigma\in
S_{|V|}\right\\})$

18: if $edgeMask=0$ then

19: $X_{\text{False}}.add(\Pi)$

20: end if

21: $X_{\text{All}}.add(\Pi)$

22: end if

23: end for

24:end for

25:$\textbf{return }X_{\text{All}}\backslash X_{\text{False}}$

At this point, all the material for the enumeration algorithm are ready. Let
us comment how Algorithm 2 works. First of all, remark that $S_{n}$ (line 5)
denotes the set of permutations of $n$ elements and $X^{\sigma}$ (lines 14 and
17) denotes the application of the permutation $\sigma$ on the set $X$. Lines
4-5 build the combinatorial objects needed for the enumeration and lines 6
through 15 construct a rotation system given those combinatorial objects. Line
17 finds the canonical form of the constructed rotation system. The set
$X_{\text{False}}$ stores the pseudo-valid (_i.e._ with Euler’s characteristic
equal $0$) systems but with a frustration of $0$, _i.e._ the ones whose a
corresponding embedding in the Klein bottle does not exists (see Theorem 3.2),
and $X_{\text{All}}$ store the pseudo-valid ones regardless of their
frustration. For sake of clarity, the two optimisations detailed above are not
integrated in the algorithm but they could intervene respectively lines 4 and
17.

##  4 The straight-line drawing algorithm

Our drawing algorithm uses the idea of _embedding extension_ : extract a
subgraph which we know how to draw and then extend the drawing by adding the
missing nodes and edges (see [11, 6, 3] for instance). Since the main
motivation of the algorithm is to draw non-planar and even non-toroidal graphs
by a straight-line drawing, we can hence take a Kuratowski subgraph, _i.e._
$K_{5}$ or $K_{3,3}$, as a base. However, to be sure to be able to draw this
subgraph according to the given rotation system, we have first to determine
all the ways to draw these two graphs on the Klein bottle. We will also make
the standard assumption that our input graph is 3-connected. If not, dummy
edges can be added to make $G$ become 3-connected, then removed at the very
end.

We introduce a notation for the drawing of a graph $G$, usable both in theory
and implementation-wise.

###### Definition 4

Let $G=\left\langle V,E\right\rangle$ be a graph, we define its drawing
$\Gamma(G)=\left\langle\gamma,\delta\right\rangle$, with
$\gamma=\left\\{\gamma_{v}\in[0,1]^{2}\mid v\in V\right\\}$, the coordinate of
the node $v$ in the Klein bottle, and
$\delta=\left\\{\delta_{e}\in\mathbb{Z}^{2}\mid e\in E\right\\}$, the shifts
of each edge defining if they go through one or multiple identified sides of
the Klein bottle.

One coordinate, $x$ or $y$ is chosen to correspond to the inverted side,
without loss of generality, say $x$. Let consider a node $v$ with coordinates
$(\gamma_{x_{v}},\gamma_{y_{v}})$ having a neighbour $u$ linked by an edge
with a $(\delta_{x},\delta_{y})$ shift. To compute the coordinates of $u$
relative to $v$, we will consider two cases:

$\gamma_{v\rightarrow
u}=\begin{cases}(\delta_{x}+\gamma_{x_{u}},\delta_{y}+\gamma_{y_{u}})&\text{$\delta_{x}$
is even}\\\
(\delta_{x}+\gamma_{x_{u}},\delta_{y}+1-\gamma_{y_{u}})&\text{$\delta_{x}$ is
odd}\end{cases}$

These relative coordinates are mainly used to draw the edges between the nodes
or to compute the center of a face. This can intuitively be extended to non-
adjacent nodes, in which case we sum up the shifts of the edges on the path
between the nodes. We assume in the following that the paths in question are
clear form the context.

As explained before, the base of our drawings are the Kuratowski subgraphs
present in our input graph. As a preprocessing step, all the possible
embeddings of $K_{5}$ and $K_{3,3}$ are precomputed in advance. This step is
executed only once by Algorithm 2, to have thereafter a usable database for
our main algorithm. After this step we are left with the $13$ embeddings ($11$
for $K_{5}$ and $2$ for $K_{3,3}$) shown in Figure 5. We will denote this set
of embeddings $\Omega$. We can note that for $K_{5}$, there are 5 more
embeddings on this surface than on the torus, described by Myrvold [11]. We
stress that these are the only possible ways, up to translation of the nodes,
to draw these graphs on the Klein bottle, meaning that when extracting our
subgraph, the given rotation system of this subgraph will necessarily
correspond to exactly one of these drawings, again up to switch-equivalence.

Figure 5: Unlabelled embeddings of $K_{5}$ and $K_{3,3}$ on the Klein bottle.

We setup the drawings of these embeddings to be convex (see Figure 6), in
order to use a Tutte-like algorithm to place the remaining nodes. Note that
having strictly convex embeddings as starting base is not mandatory especially
as the extracted subgraph homeomorphic to $K_{5}$ or $K_{3,3}$ could
potentially have nodes of degree 2 which would lead to non-strictly convex
embeddings. The following Theorem ensures that the final drawing is equivalent
to the rotation system given in input, since it proves that for each of the
locally planar and orientable faces there exists a unique non-intersecting
drawing.

Figure 6: Strictly convex unlabelled embeddings of $K_{5}$ and $K_{3,3}$ on
the Klein bottle.

###### Theorem 4.1

Let $G=\left\langle V,E\right\rangle$ be a graph, and $f$ a convex 2-cell
region of the Klein bottle bounded by a fixed cycle $C$ of G. Let $H$ be the
subset of the nodes of $G$ that has to be embed in $f$. If $G$ is 3-connected,
then there exist a unique planar embedding of the subgraph of $G$ induced by
$H\cup C$ where all the nodes of $H$ are in the same side of $C$.

###### Proof

First, let $v$ be a node on $C$ and $u$ a node adjacent to $v$. The node $v$
can potentially appear multiple times on $C$, however each of the possible
attachments corresponds to a distinct position in $\pi_{v}$. Knowing $\pi_{v}$
allows to know on which occurrence of $v$ in $C$ $u$ must be attached. Thus,
the ambiguity on the multiplicity of any node on the boundary of $f$ can be
cleared up. Let assume now the $v$ can be embedded in two different faces, the
one dictated by $\Pi(G)$ and another face of $\Pi(G-u)$ which contradicts
$\Pi(G)$. Since $G$ is 3-connected, $u$ has at least three neighbours, let say
$w_{1}$,$w_{2}$ and $w_{3}$ be those neighbours. If both embeddings are
locally planar, both faces have on their boundary all the $w_{i}$. Let $P$ be
a path in $G-u$ starting and ending on $C$ and containing all the $w_{i}$.
Wlog, let $w_{1}$ and $w_{3}$ be such $w_{2}$ is included in the subpath of
$P$ starting from $w_{1}$ and ending with $w_{3}$. Let assume removing the
nodes $w_{1}$ and $w_{3}$ does not disconnect $G$ since it is 3-connected,
then there must be a path connecting $w_{2}$ to $C$. However if $u$ can be
embedded in both faces, the edges $(u,w_{1})$ and $(u,w_{3})$ must intersect
this path, which is a contradiction.

Algorithm 3 Drawing from Rotation System

1:$G=\left\langle V,E\right\rangle,\Pi(G),\Omega$

2:$\Gamma(G)$

3:$H\leftarrow\texttt{KURATOWSKI\\_SUBGRAPH}(G)$

4:$\tilde{H}\leftarrow\texttt{SMOOTHED}(H)$

5:for $\Pi(K)\in\Omega$ do

6: if $\Pi(K)\cong\Pi(G)$ then

7: $\Gamma(\tilde{H})\leftarrow\Gamma(K)$

8: end if

9:end for

10:for $v\in V$ do

11: if $v\in H$ and $v\notin\tilde{H}$ then

12: $u,w\leftarrow\texttt{GET\\_CHAIN\\_ENDPOINTS}(v)$

13: $\gamma_{v}\leftarrow(\gamma_{u}+(\gamma_{u\rightarrow
w}-\gamma_{u})*\frac{P_{uw}.index(v)}{|P_{uw}|})\mod 1$

14: end if

15:end for

16:for $(u,v)\in E$ do

17: if $u\in H$ and $v\in H$ and $(u,v)\notin H$ then

18: $\delta_{(u,v)}\leftarrow\lfloor\gamma_{u\rightarrow v}\rfloor$

19: end if

20:end for

21:for $v\in V$ do

22: if $v\notin H$ then

23: $F\leftarrow\texttt{GET\\_FACE}(\Pi(G),H,v)$

24: $\gamma_{v}\leftarrow(\sum_{u\in F}{\gamma_{u}/|F|})\mod 1$

25: end if

26:end for

27:$\Gamma_{0}\leftarrow\Gamma(G)$

28:$\Gamma_{1}\leftarrow\texttt{TUTTE}(\Gamma_{0})$

29:$i\leftarrow 0$

30:while $\Gamma_{i}\neq\Gamma_{i+1}$ do

31: $\Gamma_{i+2}\leftarrow\texttt{TUTTE}(\Gamma_{i+1})$

32: $i\leftarrow i+1$

33:end while

At this point we have all the main ingredients for our drawing algorithm. We
assume to have the following routines:

  * •

KURATOWSKI_SUBGRAPH which extract a subgraph of $G$ homeomorphic to a
Kuratowski subgraph.

  * •

SMOOTHED which takes a graph and returns a new one where all nodes of degree 2
have been replaced by an edge linking their two neighbours.

  * •

GET_CHAIN_ENDPOINTS which takes a node of degree 2 and returns the two
endpoints of the chain on which the node is.

  * •

GET_FACE computes, according to the order of the adjacency lists of the
already fixed nodes, the face in which a node has to be embedded.

  * •

TUTTE which moves all the non-fixed nodes to the barycenter of the positions
of its neighbours. See [14] for more details about Tutte’s algorithm.

Moreover, the computation of the center of a face (line 24) and the TUTTE
(line 31) subroutine are performed according to the edges shifts as said
before. For a face, we consider one point of the face in the square and get
the coordinates of the other nodes by running through the edges and keeping
track of the shifts of the edges. For the TUTTE routine, if a node $v$ would
exit the $[0,1]$ square with this routine, its $\gamma_{v}$ and the shifts of
its incident edges would have to be managed accordingly to maintain the
coherence of $\Gamma(G)$.

###### Proposition 1

Algorithm 3 runs in linear time in the number of edges of the input graph $G$.

###### Proof

The Kuratowski subgraph extraction can be done in linear time (see [16, 17]
for details). The search for the base drawing (lines 5-8) is a comparison with
a finite set of small graphs and hence, can be considered in constant time.
Then, the drawing of the remaining nodes of the Kuratoswki subgraph (lines
10-15) can be done linearly if we don’t recompute the chains each time. The
drawing of the edges not present in the Kuratowsi subgraph but whose endpoints
are (lines 16-20) needs only a run through the boundary of the faces. Finding
the faces of the remaining nodes (lines 21-26) can also be done linearly
thanks to memoization. Finally, applying Tutte’s algorithm on the non-fixed
nodes is also linear, one can stop once each node has been moved at least once
to ensure linearity. Thus, the total complexity of this algorithm is therefore
in $O(n+m)$ with $n$ the number of nodes and $m$ the edges.

##  5 Conclusions

We have highlighted the interest of having an algorithm for constructing
straight-line representations of graphs on the Klein bottle. We proposed an
algorithm to compare two general rotation systems and another one to enumerate
all the possible ones of a given graph on a given surfaces, the latter using
notions coming from the domain of signed graphs to be slightly more optimized
than a naive one. We presented also and above all an algorithm to draw a
graph, given its rotation system, and build a representation equivalent to it.

This work can be extended along several directions. The first one consists in
characterizing more classes of graphs which are non-toroidal but embeddable in
the Klein bottle. Another interesting theoretical question would be to have
more tight bounds for the number of distinct unlabelled embeddings of a graph
on the Klein bottle or on other surfaces, following on from works already done
on similar questions [2, 5]. Finally, one could study if our algorithm can be
extended to surfaces of higher genera or if the flat representation of these
surfaces, with more sided polygons, would lead to insoluble problems.

## References

  * [1] Noga Alon and Joel Harold Spencer.  The probabilistic method.  John Wiley & Sons, 2016.
  * [2] Olivier Bernardi and Guillaume Chapuy.  Counting unicellular maps on non-orientable surfaces.  Advances in Applied Mathematics, 47(2):259–275, 2011.
  * [3] Georges Demoucron, Yves Malgrange, and R. Pertuiset.  Graphes planaires.  Rev. Française Recherche Opérationnelle, 8:33–47, 1964\.
  * [4] István Fáry.  On straight-line representation of planar graphs.  Acta Sci. Math., pages 229–233, 1948.
  * [5] Jonathan L Gross and Thomas W Tucker.  Enumerating graph embeddings and partial-duals by genus and euler genus.  Enumer. Combin. Appl, 1(1), 2020.
  * [6] Martin Juvan and Bojan Mohar.  An algorithm for embedding graphs in the torus.  preprint, 2:34–49, 1998.
  * [7] William Kocay, Daniel Neilson, and Ryan Szypowski.  Drawing graphs on the torus.  Ars Combinatoria, 59(2):259–277, 2001.
  * [8] Brendan Damien McKay and Adolfo Piperno.  Practical graph isomorphism, ii.  Journal of Symbolic Computation, 60:94–112, 2014.
  * [9] Bojan Mohar.  Straight-line representations of maps on the torus and other flat surfaces.  Discrete Mathematics, 155(1-3):173–181, 1996.
  * [10] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces.  2001\.
  * [11] Wendy Joanne Myrvold and Jennifer Woodcock.  A large set of torus obstructions and how they were discovered.  Electron. J. Comb., 25:1, 2018.
  * [12] Ronald Cedric Read.  A new method for drawing a planar graph given the cyclic order of the edges at each vertex.  Congressus Numerantium, 56:31–44, 1987.
  * [13] Adrian Riskin.  On the nonembeddability and crossing numbers of some toroidal graphs on the klein bottle.  Discrete Mathematics, 234(1-3):77–88, 2001.
  * [14] William Thomas Tutte.  How to draw a graph.  Proceedings of the London Mathematical Society, S3-13(1):743–767, 1963.
  * [15] Klaus Wagner.  Bemerkungen zum vierfarbenproblem.  Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26–32, 1936.
  * [16] Stanley Gill Williamson.  Embedding graphs in the plane—algorithmic aspects.  In Annals of Discrete Mathematics, volume 6, pages 349–384. Elsevier, 1980.
  * [17] Stanley Gill Williamson.  Depth-first search and kuratowski subgraphs.  Journal of the ACM (JACM), 31(4):681–693, 1984.