\section{Introduction}


In this article, a graph $ G $ stands for a \textbf{connected multigraph} $ G = (V_{G}, E_{G}, r_{G}) $, where 
\begin{itemize}
\item $ V_{G} $ is a finite set of vertices, 
\item $ E_{G} $ is a finite set of edges, 
\item $ r_{G} $ is a map from $ E_{G} $ to $ \binom{V_{G}}{2} $, the collection of subsets of $ V_{G} $ consisting of $ 2 $ elements. 
\end{itemize}
Note that $ r_{G}(e) $ represents the endvertices of the edge $ e $. 
Also note that every edge is identified and loops are not allowed. 

Let $ n $ be a positive integer and suppose that $ V_{G} = [n] \coloneqq \{1, 2, \dots, n\} $. 
When an edge $ e \in E_{G} $ satisfies $ r_{G}(e) = \{u,v\} $, we associate the transposition $ \tau_{e} \coloneqq (u \ v) \in S_{n} $ with the edge $ e $, where $ S_{n} $ denotes the symmetric group of degree $ n $. 

An \textbf{edge ordering} of a graph $ G $ is a linear order $ \leq_{\omega} $ on $ E_{G} $, denoted as a sequence $ \omega = (e_{1}, \dots, e_{m}) $ in which $ e_{i} \leq_{\omega} e_{j} $ if and only if $ i \leq j $. 
Given an edge ordering $ \omega = (e_{1}, \dots, e_{m}) $, we associate the product $ \pi_{\omega} \coloneqq \tau_{e_{m}} \cdots \tau_{e_{1}} \in S_{n} $. 

\begin{definition}
A permutation $ \sigma \in S_{n} $ is called a \textbf{full cyclic permutation} if $ \sigma $ is a cyclic permutation of length $ n $. 
An edge ordering $ \omega = (e_{1}, \dots, e_{m}) $ of a graph $ G $ is a \textbf{full cyclic permutation ordering} if the corresponding permutation $ \pi_{\omega} = \tau_{e_{m}} \cdots \tau_{e_{1}} $ is a full cyclic permutation. 
\end{definition}

D{\'e}nes proved the following theorem to state a connection between labeled trees and factorization of a full cyclic permutation into transpositions. 
\begin{theorem}[D{\'e}nes \cite{denes1959representation-potmiothaos}. See also {\cite[Section 2]{moszkowski1989solution-ejoc}} and {\cite[Lemma 2.1]{pawlowski2022chromatic-ac}}]\label{Denes}
Given a graph $ G $, the following are equivalent. 
\begin{enumerate}[(i)]
\item Any edge ordering of $ G $ is a full cyclic permutation ordering. 
\item $ G $ is a tree. 
\end{enumerate}
\end{theorem}

\begin{figure}[t]
\centering
\begin{minipage}[b]{0.45\linewidth}
\centering
\begin{tikzpicture}
\draw (-1.6,  0.5) node[v](1){} node[above]{$ 1 $};
\draw (-1.6, -0.5) node[v](2){} node[below]{$ 2 $};
\draw (     0,    0) node[v](3){} node[above]{$ 3 $};
\draw ( 1.6,  0.5) node[v](4){} node[above]{$ 4 $};
\draw ( 1.6, -0.5) node[v](5){} node[below]{$ 5 $};
\draw (1)--(2) node[midway, xshift=-8, yshift=0]{$ e_{1} $};
\draw (2)--(3) node[midway, xshift=2, yshift=-6]{$ e_{2} $};
\draw (3)--(4) node[midway, xshift=-2, yshift=6]{$ e_{3} $};
\draw (4)--(5) node[midway, xshift=8, yshift=0]{$ e_{4} $};
\draw (1)--(3) node[midway, xshift=2, yshift=6]{$ e_{5} $};
\draw (3)--(5) node[midway, xshift=-2, yshift=-6]{$ e_{6} $};
\end{tikzpicture}
\caption{A butterfly graph.}
\label{fig: butterfly graph}
\end{minipage}
\begin{minipage}[b]{0.45\linewidth}
\centering
\begin{tikzpicture}
\draw (-1.6,  0.5) node[v](1){};
\draw (-1.6, -0.5) node[v](2){} node[below]{\rule{0mm}{3mm}};
\draw (   0,    0) node[v](3){};
\draw (   1.6,    0) node[v](4){};
\draw ( 3.2,  0.5) node[v](5){};
\draw ( 3.2, -0.5) node[v](6){};
\draw (3)--(1)--(2)--(3)--(4)--(5)--(6)--(4);
\end{tikzpicture}
\caption{A dumbbell graph.}
\label{fig: dumbbell graph}
\end{minipage}
\end{figure}

Note that Theorem \ref{Denes} plays an important role in the studies of the chromatic symmetric functions and the chromatic operator for trees \cite{pawlowski2022chromatic-ac,foley2022transplanting}. 
Also, note that recently the second author \cite{uchiumi2022signed} studied an analogue of Theorem \ref{Denes} for signed graphs and the hyperoctahedral group. 

It is a natural question to ask what graphs admit a full cyclic permutation ordering. 
For example, let $ G $ be the butterfly graph pictured in Figure \ref{fig: butterfly graph} and define the edge ordering $ \omega $ by $ \omega \coloneqq (e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}) $. 
Then 
\begin{align*}
\pi_{\omega} = \tau_{e_{6}} \tau_{e_{5}} \tau_{e_{4}} \tau_{e_{3}} \tau_{e_{2}}\tau_{e_{1}} 
= (3 \ 5) (1 \ 3) (4 \ 5) (3 \ 4) (2 \ 3) (1 \ 2)
= (1 \ 3 \ 2 \ 5 \ 4). 
\end{align*}
Therefore $ \omega $ is a full cyclic permutation ordering of the butterfly graph $ G $. 

When a graph $ G $ has a full cyclic permutation ordering, considering the signature of a full cycle, we can see that the Betti number $ \beta(G) $ is even. 
However, the converse is false. 
For example, one can show that the dumbbell graph (Figure \ref{fig: dumbbell graph}) has no full cyclic permutation orderings although its Betti number is $ 2 $. 



We regard a graph as a topological space by identifying each edge with the unit interval $ [0,1] $ and gluing them at vertices. 
In this article, we will show that having a full cyclic permutation ordering is a topological property as follows. 

Let $ \Sigma $ be an orientable closed surface and $ \iota \colon G \to \Sigma $ an embedding. 
We call a connected component of the complement of the image of $ \iota $ a \textbf{face}. 
An embedding $ \iota $ is a \textbf{$ 2 $-cell embedding} if every face is homeomorphic to an open disk. 
For any $ 2 $-cell embedding $ \iota \colon G \to \Sigma $, 
\begin{align*}
|V_{G}| - |E_{G}| + f_{\iota} = 2-2 g_{\Sigma}, 
\end{align*}
where $ f_{\iota} $ denotes the number of faces of the $ 2 $-cell embedding $ \iota $ and $ g_{\Sigma} $ the genus of $ \Sigma $. 
Let $ \beta(G) \coloneqq |E_{G}| - |V_{G}| + 1 $ denote the \textbf{Betti number} (also called the \textbf{circuit rank}) of the connected graph $ G $. 
Then
\begin{align*}
2g_{\Sigma} + f_{\iota} = \beta(G) + 1. 
\end{align*}
Therefore maximizing the genus $ g_{\Sigma} $ is equivalent to minimizing the number of faces $ f_{\iota} $ and hence the \textbf{maximum genus} $ \gamma_{\mathrm{max}}(G) $, the  maximum of genus $ g_{\Sigma} $ such that there exists a $ 2 $-cell embedding $ G \to \Sigma $, satisfies 
\begin{align*}
\gamma_{\mathrm{max}}(G) \leq \left\lfloor \dfrac{\beta(G)}{2} \right\rfloor
\end{align*}
holds, where $ \lfloor \ \rfloor $ denote the floor function. 
If the equality holds, then we say that $ G $ is \textbf{upper embeddable}. 
Here is the main theorem of this article. 

\begin{theorem}\label{main theorem: full cyclic}
Given a graph $ G $, the following are equivalent. 
\begin{enumerate}[(1)]
\item\label{main theorem: full cyclic 1} $ G $ has a full cyclic permutation ordering. 
\item\label{main theorem: full cyclic 2} There exists a $ 2 $-cell embedding $ \iota \colon G \to \Sigma $ such that $ f_{\iota} = 1 $. 
\item \label{main theorem: full cyclic 3} $ \beta(G) $ is even and $ G $ is upper embeddable, that is, $ \beta(G) = 2 \gamma_{\mathrm{max}}(G) $. 
\end{enumerate}
\end{theorem}

Note that the equivalence of (\ref{main theorem: full cyclic 2}) and (\ref{main theorem: full cyclic 3}) is trivial by the definition of the upper embeddability. 
Figure \ref{fig: embedding} shows how the butterfly graph can be embedded into a torus with exactly one face. 

\begin{figure}[t]
\centering
\begin{tikzpicture}[baseline=-43]
\draw (-1.6,  0.5) node[v](1){} node[above]{$ 1 $};
\draw (-1.6, -0.5) node[v](2){} node[below]{$ 2 $};
\draw (     0,    0) node[v](3){} node[above]{$ 3 $};
\draw ( 1.6,  0.5) node[v](4){} node[above]{$ 4 $};
\draw ( 1.6, -0.5) node[v](5){} node[below]{$ 5 $};
\draw (1)--(2);
\draw (2)--(3);
\draw (3)--(4);
\draw (4)--(5);
\draw (1)--(3);
\draw (3)--(5);
\draw[right hook->] (3,0) -- (5,0);
\end{tikzpicture}
\qquad
\begin{tikzpicture}
\draw (0,0) ellipse (2.5 and 1.5);
\draw (-1.2,0.1) to[out=320,in=220] (1.2,0.1);
\draw (-1.08,0) to[out=40,in=140] (1.08,0);
\draw[very thick] (0,-0.35) to[out=330,in=30] (0,-1.5);
\draw[dotted,very thick] (0,-0.35) to[out=210,in=150] (0,-1.5);
\draw[very thick] (0,0) ellipse (1.8 and 1);
\draw (0.29,-0.98) node[circle, draw, inner sep=1.5pt, minimum size=2pt, fill=black](){};
\draw (0.22,-0.62) node[circle, draw, inner sep=1.5pt, minimum size=2pt, fill=black](){};
\draw (0.2,-1.3) node[circle, draw, inner sep=1.5pt, minimum size=2pt, fill=black](){};
\draw (0,-1) node[circle, draw, inner sep=1.5pt, minimum size=2pt, fill=black](){};
\draw (0.55,-0.95) node[circle, draw, inner sep=1.5pt, minimum size=2pt, fill=black](){};
\draw (0.38, -0.66) node[scale=0.5](){$ 1 $}; 
\draw (0.35, -1.4) node[scale=0.5](){$ 2 $}; 
\draw (0.38, -1.17) node[scale=0.5](){$ 3 $};
\draw (0, -1.2) node[scale=0.5](){$ 4 $}; 
\draw (0.6, -1.15) node[scale=0.5](){$ 5 $}; 
\end{tikzpicture}
\caption{A $ 2 $-cell embedding of the butterfly graph into a torus with exactly one face. }
\label{fig: embedding}
\end{figure}

Upper embeddable graphs are well-studied objects by many researchers \cite{
huang2000face-joctsb
,jungerman1978characterization-totams
,nebesky1981every-jogt
,nebesky1983note-cmj
,nebesky1985locally-cmj
,payan1979upper-dm,
skoviera1991maximum-dm
,skoviera1992decay-ms
,skoviera1989maximum-dm
,xuong1979how-joctsb
,xuong1979upper-embeddable-joctsb
}. 
Using the characterization by Jungerman \cite[Theorem 2]{jungerman1978characterization-totams}, we have the following corollary. 

\begin{corollary}
Given a graph $ G $, the following are equivalent. 
\begin{enumerate}[(1)]
\item $ G $ has a full cyclic permutation ordering. 
\item There exists a spanning tree $ T $ of $ G $ such that every connected components of $ G \setminus T $ consists of an even number of edges. 
\end{enumerate}
\end{corollary}




The organization of this article as follows. 
In Section \ref{section: topological invariance}, we will prove a key lemma which shows having full cyclic permutation ordering is invariant under homeomorphism. 

In Section \ref{section: embedding and rotation system}, we will review the relation of $ 2 $-cell embeddings and rotation systems. 
Moreover, we will give the proof of Theorem \ref{main theorem: full cyclic}. 

In Section \ref{section: identity permutation ordering}, we will study another extreme condition, that is, edge orderings $ \omega $ such that $ \pi_{\omega} $ is the identity permutation, which Eden \cite{eden1967relation-joct} studied. 
Eden gave necessary conditions for such orderings and asked whether the condition is also sufficient. 
We will give a counter example for this question. 


\section{Topological invariance of having a full cyclic permutation ordering}\label{section: topological invariance}

\begin{proposition}\label{circular shift}
Let $ G $ be a graph and $ \omega = (e_{1}, e_{2}, \dots, e_{m}) $ a linear order on $ E_{G} $. 
Suppose that $ \omega^{\prime} = (e_{2}, \dots, e_{m}, e_{1}) $ is a the circular shift of $ \omega $. 
Then the cycle types of $ \pi_{\omega} $ and $ \pi_{\omega^{\prime}} $ coincide. 
In particular, $ \ell_{\omega} = \ell_{\omega^{\prime}} $. 
\end{proposition}
\begin{proof}
Let $ \pi_{\omega} = \tau_{e_{m}} \cdots \tau_{e_{2}}\tau_{e_{1}} $ be the corresponding permutation. 
Then $ \pi_{\omega^{\prime}} = \tau_{e_{1}}\tau_{e_{m}} \cdots \tau_{e_{2}} = \tau_{e_{1}}\pi_{\omega}\tau_{e_{1}}^{-1} $. 
Therefore $ \pi_{\omega^{\prime}} $ is a conjugate of $ \pi_{\omega} $ and hence the cycle types coincide. 
\end{proof}

\textbf{Subdivision} of an edge $ e $ in a graph $ G $ with endvertices $ \{u,v\} $ is an operation that replaces $ e $ by edges $ e^{\prime}, e^{\prime\prime} $ with endvertices $ \{u, w\} $ and $ \{v, w\} $ with a new vertex $ w $. 
The converse operation is called \textbf{smoothing}. 

A graph $ G^{\prime} $ is called a \textbf{subdivision} of $ G $ if $ G^{\prime} $ is obtained from $ G $ by taking subdivisions several times. 
It is well known that two graphs $ G $ and $ H $ are homeomorphic as topological spaces if and only if they have a isomorphic subdivision.

In order to prove that having a full cyclic permutation ordering is a topological property, it is sufficient to show that the property is invariant under subdivision and smoothing. 
In the rest of this section, we will assume the following conditions. 

\begin{itemize}
\item $ e $ is an edge of a graph $ G $ with $ r_{G}(e) = \{u,v\} $. 
\item $ G^{\prime} $ is a graph obtained by subdivision of $ e $ with an additional vertex $ w $. 
\item $ e $ is subdivided into $ e^{\prime}, e^{\prime\prime} $ such that $ r_{G}(e^{\prime}) = \{u,w\} $ and $ r_{G}(v) = \{v,w\} $. 
\end{itemize}

\begin{proposition}\label{subdivision}
For any edge ordering $ \omega $ of $ G $, there exists an edge ordering $ \omega^{\prime} $ of $ G^{\prime} $ such that $ \ell_{\omega^{\prime}} = \ell_{\omega} $. 
\end{proposition}
\begin{proof}
Suppose that $ \omega $ is an edge ordering of $ G $. 
By Proposition \ref{circular shift}, we may assume that the minimal element with respect to $ \omega $ is $ e $ and hence $ \omega = (e, e_{1}, \dots, e_{m}) $. 
Then $ \pi_{\omega} = \sigma(u \ v) $, where $ \sigma \coloneqq \tau_{e_{m}} \cdots \tau_{e_{1}} $. 
Define the edge ordering $ \omega^{\prime} $ of $ G^{\prime} $ by $ \omega^{\prime} \coloneqq (e^{\prime}, e^{\prime\prime}, e_{1}, \dots, e_{m}) $. 
Then 
\begin{align*}
\pi_{\omega^{\prime}}
&= \sigma(v \ w)(u \ w)
= \pi_{\omega}(u \ v)(v \ w)(u \ w)
= \pi_{\omega}(v \ w). 
\end{align*}

Let $ (v \ a_{1} \ \dots \ a_{s}) $ denote the cyclic permutation containing $ u $ in the cycle decomposition of $ \pi_{\omega} $. 
We can write $ \pi_{\omega} = \nu (u \ a_{1} \ \dots \ a_{s}) $, where $ \nu $ denotes the product of the other cyclic permutations in the cycle decomposition. 
Since $ \pi_{\omega}(w) = w $, 
\begin{align*}
\pi_{\omega^{\prime}} = \pi_{\omega}(v \ w)
= \nu (v \ a_{1} \ \dots \ a_{s})(v \ w)
= \nu (v \ w \ a_{1} \ \dots \ a_{s}). 
\end{align*}
Thus $ \ell_{\omega^{\prime}} = \ell_{\omega} $. 
\end{proof}

\begin{proposition}\label{smoothing}
Let $ \omega^{\prime} $ be an edge ordering of $ G^{\prime} $ such that $ \pi_{\omega^{\prime}} $ has no fixed points. 
Then there exists an edge ordering $ \omega $ of $ G $ such that $ \ell_{\omega} = \ell_{\omega^{\prime}} $. 
\end{proposition}
\begin{proof}
First note that by Proposition \ref{circular shift}, any circular shift does not change the cycle types of $ \pi_{\omega} $ and hence the property of having no fixed points. 
Therefore we may suppose 
\begin{align*}
\omega^{\prime} = (e^{\prime}, e_{1}, \dots, e_{k}, e^{\prime\prime}, e_{k+1}, \dots, e_{m}). 
\end{align*}
We will show that the edge orderings
\begin{align*}
\omega_{1} \coloneqq (e, e_{1}, \dots, e_{k}, e_{k+1}, \dots, e_{m}) \quad \text{ and } \quad 
\omega_{2} \coloneqq (e_{1}, \dots, e_{k}, e, e_{k+1}, \dots, e_{m}) 
\end{align*}
satisfy $ \ell_{\omega_{1}} = \ell_{\omega_{2}} = \ell_{\omega^{\prime}} $ by induction on $ k $, the number of edges between $ e^{\prime} $ and $ e^{\prime\prime} $ in the edge ordering $ \omega^{\prime} $. 
When $ k=0 $, that is, $ \omega^{\prime} = (e^{\prime}, e^{\prime\prime}, e_{1}, \dots, e_{m}) $, we have $ \omega \coloneqq \omega_{1} = \omega_{2} = (e, e_{1}, \dots, e_{m}) $ and $ \pi_{\omega^{\prime}} = \pi_{\omega}(v \ w) $. 
Therefore $ \ell_{\omega} = \ell_{\omega^{\prime}} $.
Assume $ k \geq 1 $. 
We will prove the claim by division into cases. 

\begin{case}\label{smoothing: case 1}
$ u \not\in r_{G}(e_{1}) $ or $ v \not\in r_{G}(e_{k}) $. 
By symmetry, we only need to prove the case $ v \not\in r_{G}(e_{k}) $. 
Define the edge ordering $ \psi^{\prime} $ of $ G^{\prime} $ and the edge orderings $ \psi_{1}, \psi_{2} $ of $ G $ by 
\begin{align*}
\psi^{\prime} &\coloneqq (e^{\prime}, e_{1}, \dots, e_{k-1}, e^{\prime\prime}, e_{k}, \dots, e_{m}), \\
\psi_{1} &\coloneqq (e, e_{1}, \dots, e_{k-1}, e_{k}, \dots, e_{m}), \\
\psi_{2} &\coloneqq (e_{1}, \dots, e_{k-1}, e, e_{k}, \dots, e_{m}). 
\end{align*}
By the induction hypothesis, we have $ \ell_{\psi_{1}} = \ell_{\psi_{2}} = \ell_{\psi^{\prime}} $. 
Since $ \tau_{e_{k}}\tau_{e^{\prime\prime}} = \tau_{e^{\prime\prime}}\tau_{e_{k}} $ and $ \tau_{e_{k}}\tau_{e} = \tau_{e}\tau_{e_{k}} $, we have $ \pi_{\psi^{\prime}} = \pi_{\omega^{\prime}} $ and $ \pi_{\psi_{2}} = \pi_{\omega_{2}} $. 
Moreover, $ \pi_{\psi_{1}} = \pi_{\omega_{1}} $ since $ \psi_{1} = \omega_{1} $. 
Therefore $ \ell_{\omega_{i}} = \ell_{\psi_{i}} = \ell_{\psi^{\prime}} = \ell_{\omega^{\prime}} $ for each $ i \in \{1,2\} $. 
\end{case}

\begin{case}
$ r_{G}(e_{1}) = \{u,x\} $ with $ x \neq v $ or $ r_{G}(e_{k}) = \{v,y\} $ with $ y \neq u $. 
By symmetry, we may suppose the former case. 
Let $ H^{\prime} $ be a graph obtained by replacing $ e_{i} $ for $ i \in \{2, \dots, k\} $ with the edge $ f_{i} $ with endvertices $ (u \ x)(r_{G}(e_{i})) $, the image of $ r_{G}(e_{i}) $ by the transposition $ (u \ x) $. 
Let $ H $ be the smoothing of $ H^{\prime} $ with respect to $ w $. 

Define the edge ordering $ \psi^{\prime} $ of $ H^{\prime} $ and the edge orderings $ \psi_{1}, \psi_{2} $ of $ H $ by 
\begin{align*}
\psi^{\prime} &\coloneqq (e^{\prime}, f_{2}, \dots, f_{k}, e_{1},  e^{\prime\prime}, e_{k}, \dots, e_{m}), \\
\psi_{1} &\coloneqq (e, f_{2}, \dots, f_{k}, e_{1}, e_{k}, \dots, e_{m}), \\
\psi_{2} &\coloneqq (f_{2}, \dots, f_{k}, e_{1},  e, e_{k}, \dots, e_{m}). 
\end{align*}
Since $ v \not\in \{u,x\} = r_{G}(e_{1}) $, $ \psi^{\prime} $ satisfies the condition for Case \ref{smoothing: case 1}. 
Therefore $ \ell_{\psi_{1}} = \ell_{\psi_{2}} = \ell_{\psi^{\prime}} $. 
Since 
\begin{align*}
\tau_{e_{1}} \tau_{f_{k}} \cdots \tau_{f_{2}}
= (u \ x)(u \ x) \tau_{e_{k}} \cdots \tau_{e_{2}}(u \ x)
= \tau_{e_{k}} \cdots \tau_{e_{2}} \tau_{e_{1}}, 
\end{align*}
we have $ \pi_{\psi^{\prime}} = \pi_{\omega^{\prime}} $ and $ \pi_{\psi_{i}} = \pi_{\omega_{i}} $ for each $ i \in \{1,2\} $ and hence $ \ell_{\omega_{i}} = \ell_{\psi_{i}} = \ell_{\psi^{\prime}} = \ell_{\omega^{\prime}} $. 
\end{case}

\begin{case}
$ r_{G}(e_{1}) = r_{G}(e_{k}) = \{u,v\} $. 
Assume $ k=1 $. 
Then $ \omega^{\prime} = (e^{\prime}, e_{1}, e^{\prime\prime}, e_{2}, \dots, e_{m}) $ and $ \pi_{\omega^{\prime}}(w) = w $. 
This contradicts to the assumption that $ \pi_{\omega^{\prime}} $ has no fixed points. 
Therefore $ k \geq 2 $. 
Let $ H^{\prime} $ be a graph obtained by removing $ e_{1}, e_{k} $ and replacing $ e_{i} $ for $ i \in \{2, \dots, k-1\} $ with the edge $ f_{i} $ with endvertices $ (u \ v)(r_{G}(e_{i})) $.  
Let $ H $ be the smoothing of $ H^{\prime} $ with respect to $ w $. 

Define the edge ordering $ \psi^{\prime} $ of $ H^{\prime} $ and the edge orderings $ \psi_{1}, \psi_{2} $ of $ H $ by 
\begin{align*}
\psi^{\prime} &\coloneqq (e^{\prime}, f_{2}, \dots, f_{k-1}, e^{\prime\prime}, e_{k+1}, \dots, e_{m}), \\
\psi_{1} &\coloneqq (e, f_{2}, \dots, f_{k-1}, e_{k+1}, \dots, e_{m}), \\
\psi_{2} &\coloneqq (f_{2}, \dots, f_{k-1}, e, e_{k+1}, \dots, e_{m}). 
\end{align*}
By the induction hypothesis, $ \ell_{\psi_{1}} = \ell_{\psi_{2}} = \ell_{\psi^{\prime}} $. 
Since 
\begin{align*}
\tau_{f_{k-1}} \cdots \tau_{f_{2}}
= (u \ v)\tau_{e_{k-1}} \cdots \tau_{e_{2}}(u \ v)
= \tau_{e_{k}}\tau_{e_{k-1}} \cdots \tau_{e_{2}}\tau_{e_{1}}, 
\end{align*}
we obtain $ \pi_{\psi^{\prime}} = \pi_{\omega^{\prime}} $ and $ \pi_{\psi_{i}} = \pi_{\omega_{i}} $ for each $ i \in \{1,2\} $ and hence $ \ell_{\omega_{i}} = \ell_{\psi_{i}} = \ell_{\psi^{\prime}} = \ell_{\omega^{\prime}} $. 
\end{case}

\end{proof}

\begin{lemma}\label{homeomorphic}
Having a full cyclic permutation ordering is a topological property. 
Namely, if graphs $ G $ and $ H $ are homeomorphic and $ G $ has a full cyclic permutation ordering, then $ H $ has a full cyclic permutation ordering. 
\end{lemma}
\begin{proof}
Since $ \omega $ is a full cyclic permutation ordering if and only if $ \ell_{\omega} = 1 $, having full cyclic permutation ordering is an invariant property under subdivision by Proposition \ref{subdivision}. 
Moreover, since every cyclic permutation has no fixed points when $ |V_{G}| \geq 2 $, having full cyclic permutation ordering is invariant under smoothing by Proposition \ref{smoothing}. 
\end{proof}

\section{Graph embeddings and rotation systems}\label{section: embedding and rotation system}

Let $ I_{v}(G) $ denote the set of edges of $ G $ incident to a vertex $ v \in V_{G} $. 
A \textbf{rotation system} of $ G $ is a collection $ \rho = (\rho_{v})_{v \in V_{G}} $ consisting of cyclic orders $ \rho_{v} $ on $ I_{G}(v) $, where a cyclic order on $ I_{G}(v) $ is an equivalence class of linear orders on $ I_{G}(v) $ obtained by identifying $ (e_{1}, e_{2}, \dots, e_{s}) $ with its circular shift $ (e_{2}, \dots, e_{s}, e_{1}) $, denoted $ [e_{1}, \dots, e_{s}] $. 

Every embedding of $ G $ to an orientable closed surface defines a rotation system with the clockwise ordering for each vertex. 
Conversely, from a rotation system we can obtain a $ 2 $-cell embedding of $ G $ on an orientable closed surface as follows. 

Define $ D_{G} $ by 
\begin{align*}
D_{G} \coloneqq \Set{(e,u,v) \in E_{G} \times V_{G} \times V_{G} | r_{G}(e) = \{u,v\}}. 
\end{align*}
We call an element of $ D_{G} $ a \textbf{dart}. 
A dart $ (e,u,v) $ shows an orientation of the edge $ e $ from $ u $ to $ v $. 
Define the involution $ \alpha $ on $ D_{G} $ by $ \alpha(e,u,v) \coloneqq (e,v,u) $. 
Given a rotation system $ \rho = (\rho_{v})_{v \in V_{G}} $, we will define bijections $ \sigma $ and $ \phi $ from $ D_{G} $ to itself. 
Suppose that $ \rho_{v} = [e_{1}, \dots, e_{s}] $ and $ r_{G}(e_{i}) = \{v, u_{i}\} $.
Define $ \sigma $ by $ \sigma(e_{i}, v, u_{i}) \coloneqq (e_{i+1}, v, u_{i+1}) $, where we consider $ e_{s+1} = e_{1} $ and $ v_{s+1} = v_{1} $. 
Let $ \phi \coloneqq \sigma \circ \alpha $. 

For every dart $ d $, the target of $ d $ coincides with the source of $ \phi(d) $ since $ \phi(e_{i}, u_{i}, v) = \sigma(e_{i}, v, u_{i}) = (e_{i+1}, v, u_{i+1}) $. 
Therefore each orbit in $ D_{G}/\langle \phi \rangle $ determines a closed walk on $ G $ and we can make a polygon whose sides are formed by the darts in the orbit. 
Gluing the sides of the polygons obtained from the orbits in $ D(G)/\langle \phi \rangle $ by the involution $ \alpha $, we obtain an embedding of $ G $ on a closed surface. 
One can show that this surface is actually orientable (See \cite[Subsection 3.2]{mohar2001graphs}) and hence this embedding is the desired $ 2 $-cell embedding. 

\begin{theorem}[See {\cite[Theorem 3.2.4]{mohar2001graphs}}]
Given a graph $ G $, there exists a one-to-one correspondence between rotation systems of $ G $ and $ 2 $-cell embeddings of $ G $ on oriented closed surfaces up to orientation-preserving homeomorphism. 
\end{theorem}

Note that, from the construction, the number of the faces of the embedding corresponding to a rotation system is equal to the number of the orbits in $ D_{G}/\langle \phi \rangle $. 

Let $ \omega $ be an edge ordering of $ G $. 
For each $ v \in V_{G} $, let $ \omega_{v} $ denote the linear order on $ I_{v}(G) $ induced by $ \omega $. 
Moreover, let $ \rho_{\omega, v} $ be the cyclic order on $ I_{v}(G) $ determined by $ \omega_{v} $. 
Thus we obtain the rotation system $ \rho_{\omega} \coloneqq (\rho_{\omega, v})_{v \in V_{G}} $ from an edge ordering $ \omega $ and hence the corresponding bijections $ \sigma_{\omega} $ and $ \phi_{\omega} = \sigma_{\omega}\alpha $. 


\begin{lemma}\label{edge ordering to rotation system}
Let $ \omega $ be an edge ordering of a graph $ G $. 
For each $ v \in V_{G} $, let $ e_{i_{v}} $ denote the minimal element of $ \omega_{v} $, that is, $ i_{v} \coloneqq \min\Set{i | e_{i} \in I_{G}(v)} $. 
Define a map $ f \colon V_{G}/\langle \pi_{\omega} \rangle \to D_{G}/\langle \phi_{\omega} \rangle $ by 
\begin{align*}
f([v]) \coloneqq [(e_{i_{v}}, v, \tau_{i_{v}}(v))], 
\end{align*}
where the brackets denote equivalence classes and $ \tau_{i} $ denotes the transposition corresponding to the edge $ e_{i} $ for each $ i $. 
Then $ f $ is a bijection. 
In particular, $ \ell_{\omega} $ equals the number of faces of the $ 2 $-cell embedding corresponding to the rotation system $ \rho_{\omega} $. 
\end{lemma}
\begin{proof}
First, we will show that the map $ f $ is well-defined. 
Fix $ v \in V_{G} $ and suppose that 
\begin{align*}
\Set{e_{i} \in E_{G} | (\tau_{i}\tau_{i-1} \cdots \tau_{1})(v) \neq (\tau_{i-1} \cdots \tau_{1})(v) } = \Set{e_{j_{1}}, e_{j_{2}}, \dots, e_{j_{k}}}
\end{align*}
with $ j_{1} < j_{2} < \dots <j_{k} $. 
Let $ v_{0} \coloneqq v $ and $ v_{p} \coloneqq \tau_{j_{p}}(v_{p-1}) $ for $ p \in \{1, \dots, k\} $. 
Then $ \pi_{\omega}(v) = v_{k} $. 
Since $ \phi_{\omega}(e_{j_{p}}, v_{p-1}, v_{p}) 
= \phi(e_{j_{p}}, v_{p}, v_{p-1})
= (e_{i_{p+1}}, v_{p}, v_{p+1}) $ for each $ p \in \{1, \dots, k-1\} $, we have $ (\alpha\phi_{\omega}^{k-1})(e_{j_{1}}, v_{0}, v_{1}) = \alpha(e_{j_{k}}, v_{k-1}, v_{k}) = (e_{j_{k}}, v_{k}, v_{k-1}) $. 
By definition, $ e_{j_{k}} $ is the maximal element in $ I_{G}(v_{k}) $ with respect to the order $ \omega_{v_{k}} $. 
Therefore $ \sigma_{\omega}(e_{j_{k}}, v_{k}, v_{k-1}) = (e_{i_{v_{k}}}, v_{k}, \tau_{i_{v_{k}}}(v_{k})) $ and hence $ \phi_{\omega}^{k}(e_{i_{v}}, v, \tau_{i_{v}}(v)) = (e_{i_{\pi(v)}}, \pi(v), \tau_{i_{\pi(v)}}(\pi(v))) $. 
Thus the map $ f $ is well-defined. 

Next, to prove the surjectivity, take $ W \in D_{G}/\langle \phi_{\omega} \rangle $. 
Suppose that $ e_{i_{W}} $ is an edge which is minimal with respect to the order $ \omega $ such that $ (e_{i_{W}}, v, \tau_{i_{W}}(v)) \in W $. 
Assume $ e_{i_{W}} $ is not minimal in $ I_{G}(v) $ with respect to $ \omega_{v} $. 
Then $ e_{j} \coloneqq \sigma_{\omega}^{-1}(e_{i_{W}}) $ is less than $ e_{i_{W}} $ with respect to $ \omega $ and $ (e_{j}, \tau_{j}(v),v) = \phi_{\omega}^{-1}(e_{i_{W}, v, \tau_{i_{W}}}(v)) \in W $. 
This contradicts to the minimality of $ e_{i_{W}} $. 
Therefore $ e_{i_{W}} $ is minimal in $ I_{G}(v) $. 
Hence $ f([v]) = [(e_{i_{W}}, v, \tau_{i_{W}}(v))] = W $. 

Finally, we prove the injectivity. 
Let $ u,v \in V_{G} $ and suppose that $ f([u]) = f([v]) $. 
Then we have $ \phi_{\omega}^{k}(e_{i_{u}}, u, \tau_{i_{u}}(u)) = (e_{i_{v}}, v, \tau_{i_{v}}(v)) $ for some $ k \in \mathbb{Z} $. 
Without loss of generality, we can assume that $ k > 0 $. 
Set $ (e_{j_{0}}, v_{0}) \coloneqq (e_{i_{u}}, u) $ and define the darts $ (e_{j_{p}}, v_{p}, \tau_{j_{p}}(v_{p})) $ by $ (e_{j_{p}}, v_{p}, \tau_{j_{p}}(v_{p})) \coloneqq 
\phi_{\omega}(e_{j_{p-1}}, v_{p-1}, \tau_{j_{p-1}}(v_{p-1})) $ for $ p \in \{1, \dots, k\} $. 
Then we obtain the sequence of edges $ (e_{j_{0}}, e_{j_{1}}, \dots, e_{j_{k}}) $. 
Note that $ (e_{j_{0}}, v_{0}) = (e_{i_{u}}, u) $ and $ (e_{j_{k}}, v_{k}) = (e_{i_{v}}, v) $. 
Suppose that 
\begin{align*}
\Set{p \in \{1, \dots, k\} | e_{j_{p-1}} >_{\omega} e_{j_{p}} }  = \{p_{1}, \dots, p_{s}\}
\end{align*}
with $ p_{1} < \dots < p_{s} = k $. 
Then $ \pi_{\omega}^{t}(v_{0}) = v_{j_{p_{t}}} $ for $ t \in \{1, \dots, s\} $. 
In particular, $ \pi_{\omega}^{s}(u) = \pi_{\omega}^{s}(v_{0}) = v_{j_{p_{s}}} = v $. 
Thus $ [u] = [v] $ and hence $ f $ is injective. 
\end{proof}

Now we are ready to prove Theorem \ref{main theorem: full cyclic}. 
\begin{theorem}[Restatement of Theorem \ref{main theorem: full cyclic}]
Given a graph $ G $, the following are equivalent. 
\begin{enumerate}[(1)]
\item\label{main theorem: full cyclic 1; restatement} $ G $ has a full cyclic permutation ordering. 
\item\label{main theorem: full cyclic 2; restatement} There exists a $ 2 $-cell embedding $ \iota \colon G \to \Sigma $ such that $ f_{\iota} = 1 $. 
\item $ \beta(G) $ is even and $ G $ is upper embeddable, that is, $ \beta(G) = 2 \gamma_{\mathrm{max}}(G) $. 
\end{enumerate}
\end{theorem}
\begin{proof}
We only need to prove the equivalence $ (\ref{main theorem: full cyclic 1; restatement}) \Leftrightarrow (\ref{main theorem: full cyclic 2; restatement}) $. 
The implication $ (\ref{main theorem: full cyclic 1; restatement}) \Rightarrow (\ref{main theorem: full cyclic 2; restatement}) $ follows by Lemma \ref{edge ordering to rotation system}. 

To prove the converse, suppose that $ G $ has a $ 2 $-cell embedding with exactly $ 1 $ face. 
Let $ G^{\prime} $ be the graph obtained by subdividing every edge of $ G $. 
Since $ G^{\prime} $ is homeomorphic to $ G $, $ G^{\prime} $ has a $ 2 $-cell embedding with exactly $ 1 $ face and the corresponding rotation system $ \rho $. 

Let $ \{v_{1}, \dots, v_{s}\} $ denote the set of vertices in $ G^{\prime} $ of degree $ 3 $ or more. 
From the construction of $ G^{\prime} $, they have no common incident edges. 
Fix a linear ordering $ \omega_{i} $ by the initial element of the cyclic ordering $ \rho_{v_{i}} $ for each $ i \in \{1, \dots, s\} $. 
Also, fix a linear ordering $ \omega^{\prime} $ on $ E_{G^{\prime}} \setminus (\bigcup_{i=1}^{s}I_{G}(v_{i})) $. 

Define the edge ordering $ \omega $ by concatenating $ \omega_{1}, \dots, \omega_{s}, \omega^{\prime} $. 
Then the corresponding rotation system $ \rho_{\omega} $ coincides with $ \rho $. 
Therefore $ \ell_{\omega} = 1 $ by Lemma \ref{edge ordering to rotation system}. 
Namely, $ G^{\prime} $ has a full cyclic permutation ordering. 
Thus we can conclude that $ G $ has a full cyclic permutation ordering by Lemma \ref{homeomorphic}. 
\end{proof}





\section{Identity permutation ordering}\label{section: identity permutation ordering}

In this section, a graph is not necessarily connected. 
We say that an edge ordering $ \omega $ of a graph $ G $ is an \textbf{identity permutation ordering} if $ \pi_{\omega} = \varepsilon $, where $ \varepsilon $ denotes the identity permutation. 
Every edgeless graph vacuously has an identity permutation ordering. 
The minimal example of a non-trivial graph having an identity permutation ordering is the dipole with $ 2 $ edges. 
Eden \cite{eden1967relation-joct} studied simple graphs that have an identity permutation ordering and mentioned the complete graph $ K_{4} $ is the minimal example. 
Figure \ref{fig: dipole and K4} shows identity permutation orderings of the dipole and $ K_{4} $. 

\begin{figure}
\centering
\begin{tikzpicture}[baseline=-36]
\draw (0,0) node[v](1){} node[above](){$ 1 $};
\draw (1.5,0) node[v](2){} node[above](){$ 2 $};
\draw (0.75, 0.45) node(){$ e_{1} $};
\draw (0.75,-0.5) node(){$ e_{2} $};
\draw (1) to[out=30, in=150] (2);
\draw (1) to[out=330, in=210] (2);
\end{tikzpicture}
\qquad
\begin{tikzpicture}
\draw (0,1.5) node[v](1){} node[above left](){$ 1 $};
\draw (0,0) node[v](2){} node[below left](){$ 2 $};
\draw (1.5,0) node[v](3){} node[below right](){$ 3 $};
\draw (1.5,1.5) node[v](4){} node[above right](){$ 4 $};
\draw (1) -- (2) node[midway, xshift=-7]{$ e_{1} $}; 
\draw (1) -- (3) node[midway, xshift=-15, yshift=7]{$ e_{3} $}; 
\draw (1) -- (4) node[midway, yshift=7]{$ e_{5} $}; 
\draw (2) -- (3) node[midway, yshift=-7]{$ e_{6} $}; 
\draw (2) -- (4) node[midway, xshift=-15, yshift=-7]{$ e_{4} $}; 
\draw (3) -- (4) node[midway, xshift=7]{$ e_{2} $}; 
\end{tikzpicture}
\caption{The dipole and the complete graph $ K_{4} $ have an identity permutation ordering.}
\label{fig: dipole and K4}
\end{figure}

Eden gave necessary conditions (without proof) for simple connected graphs having an identity permutation ordering as follows. 
\begin{proposition}[{Eden \cite[P. 130]{eden1967relation-joct}}]\label{Eden's conditions}
Let $ G $ be a simple connected graph on $ n $ vertices with $ m $ edges. 
If $ G $ has an identity permutation ordering, then the following conditions hold. 
\begin{enumerate}[(1)]
\item $ m $ is even. 
\item There exist a set $ \mathcal{C} $ consisting of closed walks and a map $ g \colon V_{G} \to \mathcal{C}$ such that the following conditions hold. 
\begin{enumerate}[(i)]
\item $ g $ is bijective. 
\item Every $ v \in V_{G} $ belongs to the closed trail $ g(v) $. 
\item The sum of the number of edges of closed trails in $ \mathcal{C} $ is $ 2m $. 
\item Each edge of $ G $ belongs to exactly two closed trails in $ \mathcal{C} $. 
\end{enumerate}
\end{enumerate}
\end{proposition}
\begin{proof}
Suppose that $ \omega = (e_{1}, \dots, e_{m}) $ be an identity permutation ordering. 
Since the identity permutation is an even permutation, we have $ m $ is even. 
Let $ f \colon V_{G} \to D_{G}/\langle \phi_{\omega} \rangle $ be the bijection considered in Lemma \ref{edge ordering to rotation system}. 
Note that $ V_{G} = V_{G}/\langle \pi_{\omega} \rangle $ since $ \pi_{\omega} = \varepsilon $. 

For each $ v \in V_{G} $, there exists no dart $ d \in D_{G} $ such that both $ d $ and $ \alpha(d) $ belong to $ f(v) $ since $ \pi_{\omega} $ is the identity. 
Thus, forgetting the direction of each dart in $ f(v) $, we obtain the closed trail $ g(v) \subseteq E_{G} $. 
Letting $ \mathcal{W} \coloneqq \Set{g(v) | v \in V_{G}} $, we have a surjection $ g \colon V_{G} \to \mathcal{W} $. 

We will prove $ g $ is injective. 
Assume that there exist distinct vertices $ u,v $ such that $ g(u) = g(v) $. 
Let $ \omega^{\prime} = (f_{1}, \dots, f_{r}) $ be the induced order of $ \omega $ on $ g(u) $. 
Since $ \pi_{\omega^{\prime}}(u) = u $ and $ g(u) = \{f_{1}, \dots, f_{r}\} $, the edges $ f_{1} $ and $ f_{r} $ are incident to $ u $. 
Also, $ f_{1} $ and $ f_{r} $ are incident to $ v $ by the same reason. 
Hence $ f_{1} $ and $ f_{r} $ are parallel edges between $ u $ and $ v $. 
This contradicts that $ G $ is simple. 
Therefore $ g $ is injective and hence bijective. 

By the definition of maps $ f $ and $ g $, every $ v \in V_{G} $ belongs to $ g(v) $. 
Moreover, 
\begin{align*}
\sum_{v \in V_{G}}|g(v)| = \sum_{v \in V_{G}}|f(v)| = |D_{G}| = 2m. 
\end{align*}
For any $ e \in V_{G} $, the two darts on $ e $ belongs distinct orbit $ f(u) $ and $ f(v) $. 
Then $ e $ belongs to $ g(u) $ and $ g(v) $ and the other trails do not contain $ e $. 
Thus the map $ g \colon V_{G} \to \mathcal{C} $ has the desired properties. 
\end{proof}

\begin{example}
For the complete graph $ K_{4} $ in Figure \ref{fig: dipole and K4}, the following map $ g $ satisfies the conditions in Proposition \ref{Eden's conditions}. 
\begin{align*}
g(1) = \{e_{1}, e_{4}, e_{5}\}, \quad
g(2) = \{e_{1}, e_{3}, e_{6}\}, \quad
g(3) = \{e_{2}, e_{4}, e_{6}\}, \quad
g(4) = \{e_{2}, e_{3}, e_{5}\}. 
\end{align*}
\end{example}

Eden asked whether the necessary conditions in Proposition \ref{Eden's conditions} are also sufficient. 
We will give a counter example for this question. 
Let $ G $ be the graph on $ 12 $ vertices with $ 20 $ edges pictured in Figure \ref{fig: counter example for Eden's question}. 
Define a map $ g $ by 
\begin{align*}
g(v_{1}) &= v_{1}v_{2}v_{10}v_{1}, \quad
g(v_{2}) = v_{2}v_{9}v_{10}v_{2}, \quad
g(v_{3}) = v_{3}v_{10}v_{4}v_{3}, \quad
g(v_{4}) = v_{4}v_{10}v_{11}v_{4}, \\
g(v_{5}) &= v_{5}v_{6}v_{12}v_{5}, \quad
g(v_{6}) = v_{6}v_{9}v_{12}v_{6}, \quad
g(v_{7}) = v_{7}v_{8}v_{12}v_{7}, \quad
g(v_{8}) = v_{8}v_{11}v_{12}v_{8}, \\
g(v_{9}) &= v_{9}v_{2}v_{1}v_{10}v_{9}, \
g(v_{10}) = v_{10}v_{3}v_{4}v_{11}v_{10}, \
g(v_{11}) = v_{11}v_{8}v_{7}v_{12}v_{11}, \
g(v_{12}) = v_{12}v_{5}v_{6}v_{9}v_{12}. 
\end{align*}

\begin{figure}[t]
\centering
\begin{tikzpicture}
\draw (-1,2) node[v](1){} node[above]{$ v_{1} $};
\draw (-2,1) node[v](2){} node[left]{$ v_{2} $};
\draw ( 1,2) node[v](3){} node[above]{$ v_{3} $};
\draw ( 2,1) node[v](4){} node[right]{$ v_{4} $};
\draw (-1,-2) node[v](5){} node[below]{$ v_{5} $};
\draw (-2,-1) node[v](6){} node[left]{$ v_{6} $};
\draw ( 1,-2) node[v](7){} node[below]{$ v_{7} $};
\draw ( 2,-1) node[v](8){} node[right]{$ v_{8} $};
\draw (-1,0) node[v](9){} node[left]{$ v_{9} $};
\draw ( 0,1) node[v](10){} node[yshift = 10]{$ v_{10} $};
\draw ( 1,0) node[v](11){} node[right]{$ v_{11} $};
\draw ( 0,-1) node[v](12){} node[yshift = -13]{$ v_{12} $};
\draw (2) -- (9) -- (10) -- (2) -- (1) -- (10) -- (3) -- (4) -- (10) -- (11) -- (4); 
\draw (6) -- (5) -- (12) -- (6) -- (9) -- (12) -- (11) -- (8) -- (12) -- (7) -- (8); 
\end{tikzpicture}
\caption{A counter example for Eden's question.}
\label{fig: counter example for Eden's question}
\end{figure}

The conditions in Proposition \ref{Eden's conditions} are satisfied. 
Suppose that $ G $ has an identity permutation ordering $ \omega $. 
By Lemma \ref{edge ordering to rotation system} there exists a $ 2 $-cell embedding $ \iota $ with $ f_{\iota} = \ell_{\omega} = 12 $ faces. 
Then the genus $ g_{\iota} $ satisfies 
\begin{align*}
2-2g_{\iota} = |V_{G}| - |E_{G}| + f_{\iota} = 12 - 20 + 12 = 4. 
\end{align*}
Therefore $ g_{\iota} = -2 $, which is a contradiction. 

\begin{problem}
Characterize graphs that have an identity permutation ordering. 
\end{problem}


\section*{Acknowledgment}
The authors wish to thank Professor Sachiko Saito for her valuable comments about topics of topology. 

\bibliographystyle{amsplain}
