% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.43}{22(3)}{2015}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx,float}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\gr}{{\rm gr}}
\newcommand\R{{\mathbb R}}
\newcommand\N{{\mathbb N}}
\newcommand{\GR}{{\cal GR}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Genus  Ranges of $4$-Regular Rigid Vertex Graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Dorothy Buck\\
\small Department of Mathematics\\[-0.8ex]
\small Imperial College London\\[-0.8ex] 
\small London, England, UK\\
\small\tt d.buck@imperial.ac.uk\\
\and
Egor Dolzhenko \\   
\small Molecular and Computational Biology Section\\[-0.8ex]
\small University of Southern California\\[-0.8ex]
\small  Los Angeles, California, U.S.A.\\
\small\tt egor.dolzhenko@gmail.com\\
\and
Nata\v{s}a Jonoska \qquad \qquad  Masahico Saito \\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small University of South Florida\\[-0.8ex]
\small Tampa, Florida, U.S.A\\
\small\tt \{jonoska,saito\}@usf.edu\\
\and
Karin Valencia\\
\small European Molecular Biology Laboratory\\[-0.8ex]
%\small Imperial College London\\[-0.8ex] 
\small Heidelberg, Germany\\
\small\tt  karin.sasaki@embl.de
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 19, 2013}{Aug 26, 2015}{Sep 4, 2015}\\
\small Mathematics Subject Classifications: 05C10, 57M15, 57M25}

\begin{document}

\maketitle


\begin{abstract}
  A rigid vertex of a graph is one that has a prescribed cyclic order 
of its incident edges. 
We study orientable  genus ranges 
of   4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values   over all orientable surfaces  into which 
a graph is embedded cellularly, and 
the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic 
order of incident edges at every vertex.
The genus ranges of 4-regular rigid vertex   
graphs are sets of consecutive 
integers, and
we address two questions: which intervals of integers appear as genus ranges of such graphs, and 
what types of  graphs realize 
a given genus range.
For graphs with $2n$  vertices ($n>1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$, 
and singletons $[h, h]$ for some $h\leq n$, 
are realized as genus ranges.
For graphs with $2n-1$  vertices ($n\geq 1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$ except 
$[0,n]$,  and 
$[h,h]$ for  some $h\leq n$, 
are realized as genus ranges.
We also provide constructions of graphs that realize these ranges. 

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Four-regular rigid vertex graphs, realization of genus ranges, unsigned Gauss codes.
\end{abstract}

\section{Introduction}




A {\it  rigid vertex} in a graph is a vertex with  a prescribed cyclic order 
(called a rotation system) of its  incident edges. 
We consider  embeddings of  4-regular rigid vertex graphs in orientable surfaces.
The notion of 4-regular rigid vertex graphs have been studied extensively in knot theory in various contexts. 
For example, 
they can be seen as   virtual link projections~\cite{Kauff}.
When a 4-regular rigid vertex graph corresponds to a virtual knot projection
(i.e., the image of a single circle),  it is called  
{\it transversely connected}. 
In this case, it is described by a double occurrence word (in which each letter appears twice), 
known as an (unsigned) Gauss code.
Transversely connected 
 4-regular rigid vertex graphs in space are also called singular knots (e.g.,\cite{Dror}). 
An embedding of a 4-regular rigid vertex graph in a surface is required to preserve the given cyclic order of edges at every vertex. 
The minimum genus of virtual knots have been studied~\cite{BDK,DK}, 
and  the  genus range
of diagrams corresponding to 
a given Gauss code is of interest in knot theory.
For example, necessary and sufficient conditions for the planarity of graphs represented by 
Gauss codes  are given in  \cite{CE1,CE2},  which in turn plays a key role in making knot tables.

Graphs with 4-valent rigid vertices and end points, called assembly graphs,  have 
been also used to model 
DNA rearrangements, in which each $4$-valent 
vertex represents a recombination site~\cite{Angeleska2007,Angeleska2009}.
Spatial embeddings of these graphs could be seen as a physical representations of 
the molecules at the moment of rearrangement, and it is of interest to study certain 
combinatorial properties and embeddings of a given graph that reflect questions from 
such biological processes. 
Genera of these graphs may measure their spatial complexity. 

The {\it genus} of a graph (also known as minimum genus) is a well-known notion in 
topological graph theory, and has been studied for a variety of ordinary 
(non-rigid vertex) graphs (e.g.,
\cite{MoharThomassenBook, gross-book}). It represents the minimum genus of a surface in 
which the graph can be embedded. 
The orientable {\it genus range} of a given graph is the set 
of all possible genera of orientable surfaces in which the graph can be embedded cellularly
(where the complement consists of open disks). 
There is a one-to-one correspondence between cellular embeddings of graphs in oriented surfaces 
and {\it rotation systems}, that specify cyclic orders (rotation schemes) of edges at each vertex \cite{MoharThomassenBook}.
In this paper we study the genus ranges of 
transversely connected 
4-regular rigid vertex graphs. 
A cellular  embedding of a 4-regular rigid vertex graph in an orientable closed surface corresponds to specifying a set of two rotation schemes at each vertex, one being the reverse of the other, while the genus ranges for ordinary graphs consider all possible rotation schemes at every vertex.
Since any embedding of rigid vertex graphs must preserve the fixed ordering of incident edges to each vertex, 
 their genus ranges are more restricted, compared to those of ordinary  (non-rigid vertex) graphs. 
For example, the graphs $\Gamma$ and  $\Gamma'$ depicted in Figure~\ref{non-rigid-vs-rigid} are isomorphic  as graphs, but not isomorphic  as rigid vertex graphs. At the vertex $v$ in $\Gamma$, the cyclic order of edges $(a, b, c, d)$ in counter-clockwise
is changed to an inequivalent cyclic order $(a,c,b,d)$ at the corresponding vertex $v'$ in $\Gamma'$.
 The genus range of $\Gamma$ and $\Gamma'$, as ordinary graphs, is $\{ 0, 1, 2\}$ and  as rigid vertex graphs, are
$\{ 1 \}$ and $\{ 0, 1 \}$, respectively. 
Hence, 
results on the genus for ordinary 
graphs 
may not be  directly applicable to rigid-vertex graphs. 
Thus in this  paper we study the genus ranges of 4-regular rigid vertex graphs. 
Other variations of restricted graph embeddings in surfaces have been studied in the literature.
In \cite{SS}, for example, 
embeddings of graphs in orientable surfaces with respect to a certain  set of {\it walks}
was defined. In our context, a walk corresponds to the  boundary curve of 
a face of the complement. 


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=3in]{non-rigid-vs-rigid.eps}\\
    \caption{ Difference of genera between regular graphs and rigid vertex graphs}\label{non-rigid-vs-rigid}
    \end{center}
\end{figure}


We  set forth the following two problems.

\begin{problem}\label{MainProblem} {\ }

\noindent
{\rm (a)} For a positive integer $n$, what  sets of integers do or do not appear as  genus ranges of 4-regular rigid vertex graphs 
with $n$ vertices?
 
\noindent
{\rm (b)} Identify the class of  4-regular rigid vertex graphs with a given genus range.

\end{problem}

With this paper we provide some answers to these questions. 
In particular, we observe 
that 
a genus range of a 4-regular rigid vertex graph is always a set of consecutive integers 
(Lemma~\ref{conseclem}). 
This result  is known~\cite{Duke1966}
for general graphs up to  graph equivalence, but it is 
a new observation for rigid vertex graphs. 
Further, we show (Theorem~\ref{mainthm}) that every set 
$\{m, m+1, \ldots, m'\}$ for $0\le m<m'\le n$ appears as a genus range of some 
transversely connected 
4-regular rigid vertex graph with $2n$ vertices. The same family, without the set $\{0,1,\ldots,n\}$, 
appears as a genus range of some 
transversely connected 
4-regular rigid vertex graph with $2n-1$ vertices. We 
also observe that 
none of such graphs 
with $2n-1$ vertices has genus range 
$\{0,\ldots, n\}$ (Lemma~\ref{fullrangelem}) nor genus range  $\{n\}$ 
(Lemma~\ref{notnnlem}). We characterize 
those graphs 
with genus range $\{0\}$ (Proposition~\ref{gr-0-lem}). 
For a given number $n$, even or odd, we leave it open to determine the numbers $h$ 
such that the set $\{ h \}$ appears as a genus range of a 
transversely connected 
4-regular rigid vertex graph of $n$ vertices.


\medskip



The paper is organized as follows. In the rest of this section we define 
transversely connected 
4-regular rigid vertex graphs, the genus range of these graphs and introduce several useful constructions. In Section~\ref{PropOfGenus} we discuss and prove general observations about properties of genus ranges of 
these graphs 
motivated by the computational studies in Table~\ref{CalculationsTable}. In Section~\ref{Realization} we prove the existence of certain genus ranges in their most general form, and in Section~\ref{Characterize}, we investigate 
which intervals of integers appear as genus ranges.
We conclude with remarks on distributions of genus ranges.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Terminology}\label{PreliminaryDefs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we define  the concepts we use in the paper, and 
introduce constructions that will be used in later sections to find various genus ranges.


\subsubsection{Four-regular rigid vertex graphs and double occurrence words}

A {\it rigid vertex} is a vertex  for which  a cyclic order (or its reverse) of its incident edges is specified.
For a  rigid  vertex that has 4 incident edges, if its incident edges appear in order
  $(e_1,e_2,e_3,e_4)$,  then the corresponding {\it rotation schemes}
   specified at this vertex 
are cyclic permutations of   $(e_1,e_2,e_3,e_4)$ and cyclic permutations of its reverse
  $(e_4,e_3,e_2,e_1)$.
 For the ordered edges   $(e_1,e_2,e_3,e_4)$,
we say that  $e_2$ and $e_4$ are  {\it neighbors} of $e_1$ and $e_3$ {\it with respect to $v$}. 
The neighboring edges are consecutive with respect to all  rotation schemes assigned to the vertex. %
  We observe that valency  $4$ is the smallest valency that makes difference in cyclic ordering
of edges and we concentrate here on 4-valent vertices only.
Two  4-regular rigid vertex  graphs are {\it isomorphic} if they are isomorphic as 
   graphs and the graph isomorphism preserves the cyclic order of the edges incident to a vertex.

A trail 
(a closed walk  with no  edge repetition) in a  graph is called a {\it transverse path}, or simply  a {\it transversal}, if   consecutive edges of the path are 
never neighbors with respect to their common incident vertex. 
For $4$-regular rigid vertex graphs, a transversal is considered as the image 
of a circle in the graph that goes through every vertex ``straight ahead'',
and takes non-consecutive edges with respect to the rotation schemes of each vertex.
A 4-regular rigid vertex graph that has an Eulerian (visiting all edges) 
 transversal is  called a 
{\it  transversely connected} 
 4-regular rigid vertex graph. 
 For a 
 transversely connected 
 4-regular rigid vertex graph, if a transversal is oriented, the graph is called {\it oriented}. 
  We note that in a  
  transversely connected 
  4-regular rigid vertex graph, if a vertex $v$ is an endpoint of
 a loop $e$, then $e$ must be a neighbor of itself. 

\medskip  
\noindent 
{\bf Convention:} In the rest of the paper,
unless otherwise stated,  all graphs
are  
transversely connected 
$4$-regular rigid vertex graphs. 
\medskip  



  {\rm A {\it double-occurrence}  word $w$ over an alphabet set  
  is a word which contains each symbol of the alphabet set exactly $0$ or $2$ times. (Double-occurrence words  are 
  also called {\it (unsigned) Gauss codes} in knot theory \cite{Kauff}.)}
 

 {\rm  Two double-occurrence words  are called equivalent  if one is obtained from the other by a sequence of the following   three operations: (1)  (bijective) renaming of the symbols,  (2) a cyclic 
  permutation,   (3) taking the reverse (e.g.,  the reverse of $w=a_1 \cdots a_k$ is $w^R=a_k \cdots a_1$). }
        For example,   $w=123231$ is equivalent to its reverse 
   $w^R=132321$ and
  $w'=213132$ is equivalent to 
    $w$ by  renaming $1$ with $2$ and $2$ with $1$. 
 
     
Double-occurrence words are related to   graphs as follows. 
Let $\Gamma$ be a 
transversely connected  
4-regular rigid vertex   graph.  Orient the graph and 
pick  a base point on the graph. Let  $\alpha = v_0, e_0, \ldots, v_n, e_n, v_0$ be an Eulerian transversal starting at the base point and let $w = v_0 \cdots v_n$ be the sequences of consecutive vertices in $\alpha$. Each vertex appears twice in $w$, therefore $w$ is a double-occurrence word over the alphabet 
consisting of the set of vertices, corresponding to the  graph $\Gamma$. 
 Conversely, for a given double-occurrence word 
 containing $n$ letters, a  graph is constructed as follows. 
 The set of vertices corresponds to the set of distinct symbols  in the double-occurrence word,
and each vertex is labeled by a symbol. 
Starting from the vertex labeled by the first symbol of the given word, connect the vertices by edges in the order 
of appearance of symbols of the word through a Eulerian transversal,   and connect the path back
to the starting vertex. In the second encounter of a vertex,  corresponding to the second appearance of the symbol in the word, the path goes straight through the vertex, 
so that the edges added in the second visit are not neighbors at that vertex.
This results in a transversely connected 4-regular rigid vertex graph.


  Equivalence classes of double-occurrence words  are in one-to-one correspondence with isomorphism classes of  
 transversely connected 
 4-regular rigid  vertex graphs  \cite{Angeleska2009}. In particular, if $w$ is a  double-occurrence word,
 we write $\Gamma_w$ for a  graph corresponding to $w$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsubsection{Genus of  transversely connected  4-regular rigid vertex  graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

An embedding of a graph in a surface is called {\it cellular} if each component of the complement of the graph in the surface is an open disk.
 For a graph $G$, the {\it minimum orientable genus of $G$}, denoted $g_{min}(G)$, is the smallest non-negative integer $g$ such that $G$ admits an 
embedding in a closed (compact, without  boundary) orientable surface $F$ of genus $g$. 
We recall 
 the following fact 
 (Proposition 3.4.1 in \cite{MoharThomassenBook}): 
Every embedding of $G$ into a minimum genus surface is 
cellular.
 The {\it maximum orientable genus of $G$}, denoted $g_{max}(G)$,
 is the largest non-negative integer $g$ such that $G$ admits a cellular embedding in a closed  orientable surface $F$ of genus $g$. 
    
   An {\it embedding of a $4$-regular rigid vertex graph} in a surface is 
   an embedding of the graph 
  such  that the cyclic order of edges at each vertex
agrees with those of the corresponding embedded images. 
 In particular, neighboring edges at a vertex belong to the boundary of a common complementary region. 

\begin{definition}\label{GenusRangeSAGs}
{\rm 
The \textit{genus range} $\gr(\Gamma)$ of  a 4-regular rigid vertex  graph $\Gamma$ 
 is the set of values of genera over all 
orientable  surfaces $F$ into which 
  $\Gamma$ 
is embedded cellularly.
We denote the family of all genus ranges of  graphs with $n$ vertices 
by ${\cal GR}_n$.
}
\end{definition}

\noindent
{\bf Convention.}   In this work, every embedding of a graph is  
a cellular 
 embedding in an orientable surface. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Preliminary constructions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this section we introduce tools to study genus ranges. 
We describe an explicit construction of a cellular embedding of a  graph, related to rotation systems of embeddings of standard graphs \cite{MoharThomassenBook,Jonoska2002,Sergei}, called the  {\it ribbon graph construction}. 
We also introduce two techniques that are used to calculate genus ranges in later sections: a {\it connection change} in Section~\ref{ConnectionChangesection} and the {\it addition and removal of a vertex} in Section~\ref{AdditionRemovalVertexsection}. Finally, we observe 
that genus ranges of  graphs consist of consecutive integers in Lemma~\ref{conseclem}.



\subsubsection{Ribbon graph construction}\label{RibbonConstructionsection}

One way to obtain a cellular embedding of 
a  graph $\Gamma$
in a compact orientable surface is by constructing a surface by connecting bands (ribbons) along the graph. 
This construction is called a {\it ribbon  construction} and is described below.

\begin{figure}[H]
    \begin{center}
   \includegraphics[width=7cm]{vert.eps}
    \caption{Ribbon graph construction for $w=u_1 ij u_2 i'j u_3$}\label{vert}
    \end{center}
\end{figure}
\vspace*{-1ex}
Let $\Gamma$ be a graph with $n$ vertices labeled from 
$1$ to $n$, and let $w$ be the  double-occurrence word 
that represents $\Gamma$ with respect to a transversal.
 To each vertex $i$, $i=1 , \ldots, n$, 
we associate  a square whose center  axes coincide with the edges incident to the vertex
as depicted in Figure~\ref{vert}. 
The bands are attached in such a way that the resulting surface is orientable.
In  Figure~\ref{vert}(A), the connection by a band is described when the vertex $j$ 
immediately follows $i$ in $w$, where    
$j$ is   
  the first occurrence in $w$. 
In Figure~\ref{vert}(B), one possibility of connecting  a band  to the vertex $j$ 
at its second occurrence is shown. 
By continuing the band attachment along a transversal, one obtains a compact surface 
with boundary which  consists of finitely many circles. 
The resulting surface is called a {\it ribbon graph}.
The ribbon graphs have been studied in literature for general graphs (see, for example, \cite{Sergei}).  


By capping the boundaries of a ribbon surface
with disks, one obtains a cellular embedding of $\Gamma$ in an orientable, 
closed (without boundary) 
surface.   
 On the other hand, for a given cellular embedding of a graph $\Gamma$, its neighborhood is regarded as a ribbon surface as described above. 
Therefore, a ribbon surface gives rise to an embedding, and any embedding of a graph in an orientable  surface corresponds to a ribbon surface. 

Note that there are two choices in connecting a band to a vertex $j$
at its second occurrence, either from the top as in Figure~\ref{vert}(B), or from the 
bottom. 
Hence 
$2^n$ ribbon graphs 
can be constructed, some of which may be homeomorphic.
 In \cite{CE1,CE2}, the two 
 possibilities 
 of connecting bands are represented by signs ($\pm$), and signed Gauss codes were
used to specify the two choices.


%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Connection change}\label{ConnectionChangesection}
%%%%%%%%%%%%%%%%%%%%%%%%




The genus range of a given  graph can be computed by finding genera of all surfaces constructed from the ribbon graph construction. 
We recall the well-known Euler characteristic formula, establishing the relation between 
the genus and the number of boundary components. 
The Euler characteristic $\chi(F)$ of a compact orientable surface
$F$ of genus $g(F)$ and the number of boundary components $b(F)$ are
related by $\chi(F)=2-2 g(F) - b(F)$. 
As a complex, $\Gamma$ is regarded as  
 a $1$-complex with $n$ vertices and $2n$
edges, and $F$ is homotopic to such a $1$-complex 
 (as a deformation retract).
Hence $\chi(F)=n - 2n=-n$.
Thus we obtain the following well known formula, which we state as a lemma, as 
we use it often in this paper. 


\begin{lemma}\label{Eulerlem}
Let $F$ be a 
 surface for a  graph $\Gamma$ obtained by the ribbon graph construction. 
Let $g(F)$ be the genus of $F$, $b(F)$ be the number of boundary components of $F$, 
and $n$ be the number of vertices of $\Gamma$.
Then we have 
$g(F) =(1/2)(n-b(F) + 2 )$. 
\end{lemma}

Therefore  the genus range of the graph $\Gamma$ can be computed  from  
 the numbers of  boundary components of all ribbon graphs of $\Gamma$,
$\{ \, b(F) \, | \, F\, ${\rm is a ribbon graph of}\,\, $ \Gamma\, \}$. 
Note that $n$ and $b(F)$ have the same parity, as genera are integers. 




\begin{figure}[H]
    \begin{center}
   \includegraphics[width=7.5cm]{flip.eps}
    \caption{Changing the connection (rotation scheme)  at a vertex }\label{flip}
    \end{center}
\end{figure}
\vspace*{-1ex}
In Figure~\ref{flip}(A) and (B), the boundary curves of a ribbon graph 
of a graph, near a vertex, are indicated.
The arrows of these boundary curves indicate orientations of the boundary components induced from 
a chosen orientation of the ribbon graph. 
If in 
Figure~\ref{vert}(B), the  direction of entering 
the vertex has been changed from top to bottom (or vise versa), 
the ribbon graph may change.  
This change 
in  
 the ribbon graph 
 is  
 illustrated 
 in Figure~\ref{flip}(B).  
  Note that the new
ribbon graph is also orientable, as indicated by the arrows on the new boundary components.
We use a schematic image in Figure~\ref{flip}(C) to indicate the changes of connections of the boundary components illustrated in Figure~\ref{flip}(B). 
We call this operation a {\it connection change}. 
%
This corresponds to changing a rotation scheme at the vertex to its reverse. % 
Thus starting from one ribbon graph for a given graph $\Gamma$, 
one obtains its genus range by computing the number of boundary components for the surfaces obtained by switching 
connections at every vertex ($2^n$ possibilities for a graph with $n$ vertices, for a positive integer $n$). 





\begin{table}[H]
$$\begin{array}{lll}
 & & {\cal GR}_n : \\
n=2 & &  \{ 0 \}, \{ 1 \}.  \\  
n=3 & & \{0\}, \{1\}, \{0,1\}, \{1,2\}.  \\
n=4 & & \{0\}, \{1\}, \{0,1\}, \{1,2\}, \{0,1,2\}.   \\
n=5 & &  \{0\}, \{1\}, \{2\}, \{0,1\}, \{1,2\}, \{2,3\}, \{0,1,2\}, \{1,2,3\}.  \\
n=6 & &   \{0\}, \{1\}, \{2\}, \{3\}, \{0,1\}, \{1,2\}, \{2,3\}, \{0,1,2\}, \{1,2,3\}, \{0,1,2,3\} .\\
n=7 & &   \{0\}, \{1\}, \{2\}, \{3\}, \{0,1\}, \{1,2\}, \{2,3\}, \{3,4\}, \\
 & &  \{0,1,2\}, \{1,2,3\}, \{2,3,4\}, \{0,1,2,3\}, \{1,2,3,4\}. \\
\end{array}$$
\caption{ Computer calculations of possible genus ranges of  graphs with $n$ vertices.}
\label{CalculationsTable}
\end{table}



The following is known for ordinary graphs, and it can be 
confirmed 
 for rigid vertex graphs by 
observing 
that the number of boundary components 
changes by at most two 
by a change of connection at a vertex. 
Similar results have been obtained in other restricted graph embeddings as well
(e.g., \cite{SS}). 


\begin{lemma}\label{conseclem}
The  genus range of any 4-regular rigid vertex graph consists of consecutive integers.
\end{lemma}

Hence, from now on  the genus range $\{ a, \ldots, b\}$, for integers $0\leq a \leq b$, is  denoted by $[a, b]$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Addition and removal of a vertex}\label{AdditionRemovalVertexsection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We investigate how the number of boundary components 
changes 
under a construction that generates a  graph with $n\pm 1$ vertices from one that has $n$ vertices.


Let $\Gamma$ be a  graph and $e, e'$ be two edges in $\Gamma$ with endpoints $v_1,v_2$ and 
$v_1',v_2'$ respectively. 
We say that $\Gamma'$ is obtained from $\Gamma$ by {\it addition of a vertex
by crossing $e,e'$ and splitting $e$ into $e_1,e_2$ and $e'$ into $e_1',e_2'$ in cyclic order 
 $e_1,  e_1',e_2, e_2'$}  (or simply {\it by addition of a vertex} when context allows) if 
 $\Gamma'$ is obtained from $\Gamma$ as depicted in Figure~\ref{add-remove} and denote it by 
 $\Gamma'=\Gamma(e, e')$. 
In this case we also say that {\it  $\Gamma$ is obtained from 
$\Gamma(e, e')$ 
by vertex removal}.
Note that the vertices $v_1, v_2, v_1', v_2'$ need not to be distinct.


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=3.5in]{add-remove-vertex.eps}
    \caption{Addition and removal of a vertex }\label{add-remove}
    \end{center}
\end{figure}

Let $F$ be a  ribbon graph of $\Gamma$  and  let $\Gamma'$ be obtained from $\Gamma$ by addition of a vertex $w$.  A  ribbon graph $F'$ of $\Gamma'$ whose boundary connections at every vertex $v\not =w$ is the same as 
the boundary connections of  $F$ at $v$ is denoted $F(w)$. Since there are two possible connections of the boundary components of $F(w)$ at the new vertex $w$, the notation indicates one of those two choices.

All possible changes in the global connections of boundary components of $F(w)$ at the new vertex $w$ relative 
to the boundary components of  the crossing edges that add the new vertex $w$ are depicted in Figure~\ref{add-vertex-strands}.
\begin{figure}[H]
    \begin{center}
   \includegraphics[width=6in]{add-vertex-strands.eps}
    \caption{Possibilities of   connections }\label{add-vertex-strands}
    \end{center}
\end{figure}

\begin{definition}\label{tracedef}
{\rm
We say that the boundary component $\delta$ of a ribbon graph  $\Gamma$ \textit{traces} the edge $e$ of $\Gamma$ if 
the boundary of the ribbon that contains $e$ is a portion of $\delta$. }
\end{definition}

 There are at most two boundary components that can trace an edge, so there are at most four boundary components of a  ribbon graph that trace two edges from $\Gamma$. 

\begin{lemma}\label{lem:add-vertex}
Let $\Gamma,\Gamma'$ be two  graphs such that $\Gamma'=\Gamma(e, e')$ 
by crossing edges $e,e'$ and addition of  a new vertex $w$. Suppose $F$ and $F(w)$ are  ribbon graphs for $\Gamma,\Gamma'$ as defined above with $b,b'$ being the number of boundary components for $F$ and $F(w)$, respectively. Then we have the following:
\begin{itemize}
\setlength{\itemsep}{-3pt}
\item[\rm (i)] If both $e$ and $e'$ are traced by only  one boundary component in $F$,  then $b'=b+1$ or $b'=b+3$.
\item[\rm (ii)] If  both $e$ and $e'$ are traced by two boundary components  in $F$, then $b'=b+1$ or $b'=b-1$.
\item[\rm (iii)] If  $e$ and $e'$ are traced by three boundary components in $F$, then $b'=b-1$.
\item[\rm (iv)] If $e$ and $e'$  are traced by four boundary components in $F$, then  $b'=b-3$.
\end{itemize}
\end{lemma}

\begin{proof}
The proof follows directly from the observations shown in 
Figure~\ref{add-vertex-strands}.
 \end{proof}
 



%%%%%%
\section{Properties of Genus Ranges}\label{PropOfGenus}
%%%%%%%



In this section we investigate properties of genus ranges that 
are used in later sections. 
Although the following lemma is a special case of Lemma~\ref{joinlem}, 
we state it separately  since 
its simple form is convenient to use. 
We recall that all graphs are transversely connected 4-regular rigid vertex graphs. % 


\begin{lemma}\label{looplem}
For any  double-occurrence word $w$, the 
 genus range 
of $\Gamma_w$ 
is equal to that of 
$\Gamma_{w'}$ where 
  $w'=waa$ and   $a$ is a  
    letter
that does not appear in $w$.
\end{lemma}
\begin{proof}
The  graph $\Gamma_{w'}$ corresponding to $w'$ is obtained from the graph $\Gamma_w$ 
by adding a 
  loop with a single vertex corresponding to the letter $a$. Both of the two 
  boundary   
   connections at the added vertex 
   $a$ 
   increase the number of boundary components by one as depicted in 
     Figure~\ref{add-vertex-strands} (b) and (h).
Hence the genus range remains unchanged.
\end{proof}


\begin{definition}\label{loopnestdef}
{\rm
A  double-occurrence word $v$ is said to be obtained from $w$ by {\it loop nesting}  if there exists a sequence  
of  double-occurrence words $w=w_0, w_1, \ldots, w_n=v$ such that $w_{i+1}=w_i' a_i a_i$ where $w_i'$ is a cyclic permutation
or reverse 
of $w_i$ and $a_i$ is a single letter that does not appear in $w_i$ for $i=0, \ldots, n-1$.  
A  double-occurrence word obtained from the empty word $\epsilon$ by loop nesting is called {\it loop-nested}.
A 4-regular rigid vertex graph corresponding to a loop-nested  double-occurrence word is called a {\it loop-nested} graph. 
}
\end{definition}

Lemma~\ref{looplem} implies that loop nesting preserves the genus ranges. Specifically,

\begin{corollary}\label{loopcor}
If a  double-occurrence word $w'$ is obtained from a  double-occurrence word $w$ by loop nesting, then their 
corresponding  graphs have the same genus range.
\end{corollary}


\begin{corollary}\label{higherlem}
If a set $A$ appears as the genus range in ${\cal GR}_n$ for a positive integer $n$, 
then $A$ appears as a genus range in ${\cal GR}_m$
for any integer $m>n$. 
\end{corollary}
\begin{proof}
Let $w'=w a_1 a_1 a_2 a_2 \cdots a_{k} a_k $ where $k=m-n>0$, then by Corollary~\ref{loopcor} 
$\Gamma_{w'}$ has the same genus range as $\Gamma_w$. 
\end{proof}



\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=3.5in]{crosssum.eps}\\
    \caption{Cross sum }\label{crosssum}
    \end{center}
\end{figure}

\begin{definition}\label{joindef}
{\rm
Let $\Gamma_1$ and $\Gamma_2$ be   graphs and $e_i$ be an edge in $\Gamma_i$ for $i=1,2$. 
A   graph $\Gamma$ is said to be obtained from $\Gamma_1$ and $\Gamma_2$ by 
a {\it cross sum} with respect to $e_1$ and $e_2$
 if it is formed by 
connecting $\Gamma_1$ and $\Gamma_2$
through a new vertex to form 
the figure-eight graph with 
$e_1$ and $e_2$, as depicted in Figure~\ref{crosssum}.
The crossing at the middle in the right of Figure~\ref{crosssum} is the 
newly added vertex. 
}
\end{definition}



The cross sum 
was discussed, in relation to virtual knots, in \cite{JSC}.
The cross sum construction depends on the choice of edges of the two graphs to
connect to the figure-eight.


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=5in]{crosssumbd.eps}\\
    \caption{Boundary curves of a cross sum construction }\label{crosssumbd}
    \end{center}
\end{figure}


\begin{lemma}\label{joinlem} 
Let $\Gamma_1$ and $\Gamma_2$ be    graphs.
If $\Gamma$ is obtained from $\Gamma_1$ and $\Gamma_2$ by a cross sum, then 
 $\gr(\Gamma)=\{ \, g_1 + g_2  \mid  g_1  \in \gr(\Gamma_1), \ g_2 \in \gr(\Gamma_2) \, \} $. 
\end{lemma}
\begin{proof}
Let $\Gamma$ be the graph obtained from $\Gamma_1$ and $\Gamma_2$ by cross sum 
 through $e_1$ and $e_2$.
For given ribbon graphs $F_1$ and $F_2$ of $\Gamma_1$ and $\Gamma_2$, respectively,
a ribbon graph $F$ of $\Gamma$ is constructed as depicted in Figure~\ref{crosssumbd}. 
The two boundary curves 
tracing the edges $e_i$ of $\Gamma_i$ ($i=1,2$) 
belong to either one component or two in each of $F_1$ and $F_2$. 
In Figure~\ref{crosssumbd}(A), the case where the two curves belong to one component for both  $\Gamma_i$,
$i=1,2$, is depicted. In (B), the case when one of the two edges is  traced  by  distinct components
($\Gamma_2$ in this figure) is depicted, and in (C), the case when the both edges are traced by  distinct components of $F_i$, 
$i=1,2$, is depicted.
{}From the figures we identify these cases (A), (B), (C) with the connection cases 
(a), (b) and (h), respectively, in Figure~\ref{strand-connection}. 
We see from Figure~\ref{strand-connection} that 
by a connection change  in 
  all these cases,   
  the number of boundary components 
  does not change.   
  Let $v_i$ and $b_i$ be the numbers of vertices and boundary components of $F_i$, $i=1,2$,
respectively, and similarly $v$, $b$ for $F$.
Then 
for all cases (A), (B) and (C)  
we have  
$v=v_1+v_2+1$ and $b=b_1+b_2 -1$.
From  Lemma~\ref{Eulerlem} 
we 
compute
$$
g(F) =   \frac{1}{2} ( v- b + 2 )  
= \frac{1}{2} ( (v_1+ v_2 + 1) - (b_1 + b_2 - 1) + 2     ) 
  =g(F_1) + g(F_2) 
$$
as desired.
\end{proof}





\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=1.5in]{connecttref.eps}\\
    \caption{Connecting a pretzel }\label{connecttref}
    \end{center}
\end{figure}



\begin{definition}\label{jpretzeldef}
{\rm
Let $\Gamma$ be a  graph, $\Gamma_0$ be the graph corresponding to the word $1212$, 
and $\Gamma'$ be the graph obtained by connecting an edge $e$ of $\Gamma$ with  
  $\Gamma_0$ as depicted in Figure~\ref{connecttref}. Then  $\Gamma'$ is said to have been obtained by {\it connecting a pretzel} to $\Gamma$.
}
\end{definition}


\begin{lemma}\label{plus1lem}
Let $\Gamma'$ be obtained from $\Gamma$ by connecting a pretzel.
Suppose $\gr(\Gamma)=[m,  n]$  
  for non-negative integers $m$ and  $n$ ($m\le n$).
If there is a minimum genus embedding of $\Gamma$ such that 
the two boundary curves tracing edge  $e$ belong to the same boundary component, then 
 $\gr(\Gamma')=[m, n+1 ]$.
Otherwise  $\gr(\Gamma')=[m+1, n+1 ]$. 
\end{lemma}
\begin{proof}
In Figure~\ref{tref}, the boundary curves corresponding to all possible connections at vertices of $\Gamma_0$
are depicted in (A) through (D). 
The number of boundary components are $3$ for (A) and (C), and $2$ for (B) and (D).
In (E) and (F), the situations of how they are connected are schematically depicted,
respectively. The Figure (E) represents (A) and (C), and (F) represents (B) and (D).

\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=9.5cm]{tref.eps}
    \caption{ Boundary curves for $1212$ }\label{tref}
    \end{center}
\end{figure}

{\rm (i)}  
Suppose $\Gamma$ satisfies the condition that for all ribbon graphs of $\Gamma$,  the two boundary curves tracing edge    $e$ belong to two distinct boundary components. %
Consider a ribbon graph $F$ for $\Gamma$ with genus $g \in \gr(\Gamma)$. 
For each ribbon graph $F_0$ in (A) through (D) of $\Gamma_0$ in Figure~\ref{tref}, we obtain a ribbon graph $F'$
of $\Gamma'$ by connecting corresponding boundaries of 
the 
ribbon graphs for $\Gamma_0$ and $\Gamma$. 
If the connection  of the boundary curves of a ribbon graph $F_0$ of $\Gamma_0$ is as in Figure~\ref{tref}(E),
then the two  curves tracing  
  $e$ become connected, 
and there is an additional component indicated by a small circle 
in the middle of (E).  
 So 
  the number of 
boundary components remains unchanged, and  the number of vertices increases by $2$.
Hence $g(F')=g+1$, and $g+1$ is an element of $\gr(\Gamma')$.
If the connection of the boundary curves of  a ribbon graph $F_0$ of $\Gamma_0$ is as in Figure~\ref{tref}(F),  then again
the number of boundary curves  of the ribbon graph for $\Gamma'$ remains the same as $F$, 
and  the number of vertices increases by $2$, so that $g(F')=g+1$,
hence $g+1$ is an element of $\gr(\Gamma')$. 
Therefore  $\gr(\Gamma)=[ m+1,  n+1 ]$.  

{\rm (ii)} 
Suppose $\Gamma$ satisfies the condition that  for some ribbon graphs of $\Gamma$,
the two boundary curves tracing edge   
 $e$ belong to the same boundary component. 
Suppose that the connection  of the boundary curves 
of a ribbon graph $F_0$ of $\Gamma_0$ is as in Figure~\ref{tref}(E). 
If 
the  boundary component of a ribbon graph $F$ for $\Gamma$
 tracing
  $e$ is connected, then 
  it becomes disconnected 
  after connecting a pretzel 
  and there is an additional component
  in $F'$.  
 Therefore the number of 
boundary components  increases by $2$, and the number of vertices increases by $2$. 
Hence $g(F')=g$, and $g$ is an element of $\gr(\Gamma')$.
If 
the  boundary component of $F$ for $\Gamma$
 tracing  $e$ is disconnected,
 then the number of 
boundary components remain unchanged, and the number of vertices increases by $2$. 
  Hence in this case $g(F')=g+1$. 
  
If the connection  of the boundary curves 
of a ribbon graph $F_0$ of $\Gamma_0$ is as in Figure~\ref{tref}(F),  then 
the number of boundary components of the ribbon graph for $\Gamma'$ remains the same as that of $F$.
In this case  the number of vertices increases by $2$, so $g(F')=g+1$,
and $g+1$ is an element of $\gr(\Gamma')$. 
Therefore  $\gr(\Gamma)=[ m,  n+1] $ or $[m+1, n+1]$. 
We note
 that the genus range of $\Gamma'$ is $[m, n+1]$ if and only if there exists a ribbon surface 
$F$ with the minimum genus $m$ such that 
$e$ is traced by a single boundary component.
\end{proof}


As to the condition (i) in 
the proof of Lemma~\ref{plus1lem}, we note the following.

\begin{lemma}\label{planarlem}
Let $\Gamma$ be a planar  graph and $e$ be an edge in $\Gamma$. 
Then  for all 
 ribbon graphs of $\Gamma$, 
there are two distinct 
boundary 
components  
 that trace $e$.
\end{lemma}
\begin{proof}
Fix a planar diagram of $\Gamma$, still denoted by $\Gamma$. 
The closure of a topological, thin  neighborhood of $\Gamma$ in the plane determines a ribbon graph $F$.
Each  boundary curve of $F$ corresponds to a region of the complement of $F$
(a connected component of $\R^2 \setminus F$)  in the plane. 
In this construction, the connection of boundary curves at every vertex 
has the form in  Figure~\ref{flip}(A).
We assign checker-board ``black" and ``white" coloring 
  to these regions (there is one, see  \cite{Kauff} for example)
  such that regions bordering the same edge have distinct colors.  
  The corresponding boundary curves of $F$ inherit this coloring. 
Hence every edge is traced by boundary components of two distinct colors. 
Let $B$ and $W$ be (disjoint, non-empty) families of boundary curves colored black and white, respectively.
Any ribbon graph $F'$ of $\Gamma$ is obtained from $F$ by changing boundary connections at some vertices. 
When we change the boundary connection at 
a vertex $v$,  
two diagonal boundary curves of the same color become connected,
see Figure~\ref{flip} (A) and (C). 
The connected curves inherit  
 the color, 
 each component of  the boundary curves 
  is colored black or white after the change, 
 and every edge of $\Gamma$ is traced by two boundary components, 
 one white and one black. 
\end{proof}



%%%%%%%%%%
\section{Realizations of Genus Ranges}\label{Realization}
%%%%%%%%%

Guided by   observations made from computer calculations (Table~\ref{CalculationsTable}),
in this section we prove general statements on  the non-existence (Section~\ref{nonexistencesec}) and existence (Section~\ref{existencesec}) of various genus ranges. 
We recall again that all graphs are transversely connected 4-regular rigid vertex graphs. % 

\subsection{Genus ranges that do not arise}\label{nonexistencesec}

In what follows, all graphs refer to
transversely connected 
 4-regular rigid vertex graphs.
 
\begin{lemma}\label{fullrangelem} 
For any positive integer $n$, there is no   graph with $2n-1$ vertices 
with genus range $[0, n]$. 
\end{lemma}
\begin{proof}
Suppose there is such a graph $\Gamma$.
Since its genus range contains $0$, $\Gamma$ is planar.
By Lemma~\ref{planarlem}, every ribbon graph of $\Gamma$ has more than one boundary component, 
and therefore, the genus cannot be $n$ by Lemma~\ref{Eulerlem}.
\end{proof}

The lemma below uses arguments and methods similar to those in~\cite{SS}.

\begin{lemma}
For every graph there is a ribbon graph with more than one boundary component.
\end{lemma}
\begin{proof}   Let $\Gamma$ be a graph with $k$ vertices. Starting from one vertex, 
we enumerate the edges of $\Gamma$ along the transversal from $1$ to $2k$. Since the transversal consists of an Eulerian path in which two consecutive edges are not neighbors, every vertex in $\Gamma$ is incident to two even numbered edges and two odd numbered edges. Moreover, the odd numbered (similarly, even numbered) edges incident to a common vertex are neighbors to each other. Let $G$ be the subgraph of 
$\Gamma$ that is induced by the odd numbered edges. 
This graph consists of $k$ vertices and $k$ edges, so it is a collection of cycles. 
For any cycle $c$ of $G$, there is a choice of connection such that 
$c$ is a boundary component of a ribbon graph $F$. 
Since this component  traces edges only in $G$,  the ribbon graph $F$ must contain boundary components that trace the edges not in $G$, hence, 
 $F$ has more than one component. 
\end{proof}

The lemma immediately implies the following. 

\begin{lemma}\label{notnnlem}
For any positive integer $n$, there is no  graph with $2n-1$ vertices 
with genus range $\{ n \}$. 
\end{lemma}


\subsection{Genus ranges that do arise }\label{existencesec}


\begin{proposition}\label{nm-prop} 
For any integer $m\geq 0$, there exists an integer $n$ such that  $\{ m \}$
is a genus range in ${\cal GR}_n$. 
\end{proposition}
\begin{proof}
Let $\Gamma_m$ be the graph obtained by connecting $m$ copies of $\Gamma_0$ in the boxes $B_1, \ldots, B_m$
as depicted by solid line in Figure~\ref{connectall}, where $\Gamma_0$ is the graph depicted  in the upper half of Figure~\ref{connecttref} 
 that corresponds to the word $1212$.
This is obtained from copies 
of  
 $\Gamma_0$ by repeated application of cross sum of Definition~\ref{joindef}.
Recall that $\Gamma_0$ has the genus range $\{ 1 \}$. 
By Lemma~\ref{joinlem}, $\Gamma_m$ has the genus range $\{ m \}$.
\end{proof}


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=3in]{connectall.eps}\\
    \caption{ Repeating cross sum}\label{connectall}
    \end{center}
\end{figure}



The following provides a characterization of graphs with genus range $\{ 0 \}$, 
giving an answer to Problem~\ref{MainProblem} (b)
for this range. 


\begin{proposition}\label{gr-0-lem}

 A  double-occurrence word $w$ is loop-nested if and only if  $\gr(\Gamma_w) = \{ 0 \}$. 

\end{proposition}

\begin{proof}

Corollary~\ref{loopcor} implies that if $w$ is loop-nested then  $\gr(\Gamma_w) = \{ 0 \}$.
The converse  follows from a known characterization of signed
 double-occurrence words corresponding to closed normal planar curves (Theorem $1$ of \cite{CE1}).
 \end{proof}


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=6in]{strand-connection.eps}\\
    \caption{Possibilities of  connections }\label{strand-connection}
    \end{center}
\end{figure}

In Figure~\ref{strand-connection}, all possibilities of global connections of local arcs for a neighborhood of a vertex corresponding to Figure~\ref{flip}(A)
are depicted in the top row, 
  and in the middle row, 
the global connections after the change of connection as in Figure~\ref{flip}(C) are depicted. 
In the bottom row, the change of the number of boundary components associated with a connection change 
is  listed. 
This list is used in the proofs below. 

\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=2.5in]{repeat.eps}\\
    \caption{Graphs for words of the form $12\cdots n 12 \cdots n$ }\label{repeat}
    \end{center}
\end{figure}


 
\begin{proposition}\label{01prop}
The graph corresponding to  any word obtained from 
$w=12\cdots n 12 \cdots n$,  for an odd integer $n$, by loop nesting 
has the genus range $[0, 1]$. 
\end{proposition}
\begin{proof}
First we show that the graph $\Gamma_n$ corresponding to  a  word 
$w=12\cdots n 12 \cdots n$ has genus range $\{0,1\}$.
We start with the planar diagram depicted in Figure~\ref{repeat}.
Boundary curves of the ribbon graph obtained as a neighborhood of $\Gamma_n$ are
depicted by dotted lines. 
When the connection of  one vertex (the vertex $1$ in Figure~\ref{repeatswitch} left) is changed,
both pairs of diagonal curves are connected from two components to one
(see Figure~\ref{strand-connection}(f)). 
Hence the number of  boundary components reduce by $2$, and the genus increases 
from $0$ to $1$ by Lemma~\ref{Eulerlem}. 


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=5in]{repeatswitch.eps}\\
    \caption{Changing connections for  repeat word graphs }\label{repeatswitch}
    \end{center}
\end{figure}


After the change at the vertex $1$, the boundary connection at every other vertex 
$2$ through $n$ is as depicted in Figure~\ref{strand-connection}(h).
Hence the number of the boundary components does not change by changing the boundary connections.
After the second change of the boundary connection at the vertex $i$, the connection at every vertex 
remains the same as in Figure~\ref{strand-connection}(h).
This property holds for odd $n$.
In Figure~\ref{repeatswitch} middle and right, changes are made at vertices $i=2$ and $3$, respectively, 
after the change at the vertex $1$. 

The statement follows from Lemma~\ref{looplem}.
\end{proof}



\begin{conjecture}\label{Conjecture1}
{\rm
Any  double-occurrence word whose 
corresponding graph has 
 genus range $[0, 1]$ is 
obtained from the word $w=12\cdots n 12 \cdots n$ for an odd integer $n$ by loop nesting.
}
\end{conjecture}





\begin{figure}[ht]
\begin{minipage}[b]{0.3\linewidth}
\centering
\includegraphics[scale=.3]{n6step1}
\caption{Proof for $P_3$}
\label{n6step1}
\end{minipage}
\begin{minipage}[b]{0.3\linewidth}
\centering
\includegraphics[scale=.2]{leftbox}
\caption{Box  (X) }
\label{leftbox}
\end{minipage}
\begin{minipage}[b]{0.36\linewidth}
\centering
\includegraphics[scale=.185]{rightbox}
\caption{Box  (Z) }
\label{rightbox}
\end{minipage}

\end{figure}


\begin{proposition}\label{halfgrprop}
For any  integer $n>1$, 
 there exists a graph
$\Gamma$ of $2n$ vertices with $\gr(\Gamma)=[0, n ]$.
\end{proposition}
\begin{proof}
Computer 
calculations in Table~\ref{CalculationsTable} show that there is a unique graph of $4$ vertices corresponding to 
$12314324$ that has genus range $\{0,1,2\}$. 
In Figure~\ref{n6step1}, a  graph $P_3$  is depicted that has the genus range $\{0, 1, 2, 3\}$.
To show this, we start with the planar diagram as depicted. 
We consider the ribbon graph that is a thin neighborhood of this planar diagram.
For this ribbon graph, the boundary connection at every vertex appears as type (A) in Figure~\ref{flip}. 
The genus of this  ribbon graph is $0$.
Each region of the diagram corresponds 
to a boundary curve of the corresponding ribbon graph.
 Four of such boundary curves (out of total $8$) are depicted by dotted lines 
in the figure, for the regions labeled by $a_1$, $a_2$, $b_1$, and $b_2$. 
 


We change the boundary connection at the vertex labeled by $v_1$
from type (A) in Figure~\ref{flip} to type (C), where the connection is  
as indicated in Figure~\ref{strand-connection}(f).  
Then as Figure~\ref{strand-connection}(f) 
 indicates, the curves  $a_1$ and $b_2$, $a_2$ and $b_1$, are connected, 
respectively, reducing the number of boundary components 
by $2$. 
This causes the increase of the genus of the new ribbon graph by $1$
by Lemma~\ref{Eulerlem}, so that the new surface has
genus $1$. 
After the connection change at $v_1$, the boundary connection at $v_2$ remains 
as in  Figure~\ref{strand-connection}(f), since the regions $b_1$, $b_2$, $c_1$, $c_2$ 
are bounded by distinct curves. 
Thus by repeating this process with vertices $v_2$ and $v_3$, 
we obtain ribbon graphs of genus $2$ and $3$, respectively. The number of boundary curves after performing the changes at $v_1$, $v_2$ and $v_3$ is $2$. 
The two components can be seen as a checkerboard coloring of the regions,
and the two boundary curves near every edge belong to distinct components  (cf. Lemma~\ref{planarlem}). 
This shows that the genus range for this graph is $\{0,1,2,3\}$. 


\begin{figure}[htb]
    \begin{center}
   \includegraphics[width=3in]{snake.eps}\\
    \caption{Inductive construction of $P_n$ }\label{snake}
    \end{center}
\end{figure}



Next we describe the  graph $P_n$ for $n>3$
as the 
 combination of three subgraphs 
 indicated in Figure~\ref{snake} as follows.
If $n$ is odd, then the subgraph in the box (X) in  Figure~\ref{snake}
is as  depicted in Figure~\ref{leftbox}(odd), and if $n$ is even,
 it is as depicted in Figure~\ref{leftbox}(even), respectively. 
The middle part in the box (Y) is as  depicted in  Figure~\ref{snake}.
The subgraph in box (Z) in   Figure~\ref{snake} is either (down) or (up) of 
  Figure~\ref{rightbox}, and the choice is determined by the number of vertices
 of  $P_n$. Specifically, for integers $k$,  $P_n$ has the following patterns in boxes (X) and (Z) in    Figure~\ref{snake}, respectively:
If $n=4k$, $4k+1$, $4k+2$, $4k+3$, respectively, the box (X) and (Z) are 
filled with (even) and  (down), (odd) and (up), (even) and (up), (odd) and (down), 
respectively. Examples for $n=6$ (even, up) and $7$ (odd, down) are depicted 
in Figure~\ref{n8} and~\ref{n14}, respectively. 


\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[scale=.25]{n12}
\caption{$P_6$}
\label{n8}
\end{minipage}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[scale=.28]{n14}
\caption{$P_7$}
\label{n14}
\end{minipage}
\end{figure}



We generalize the argument for $P_3$ to $P_n$ inductively.
We start with the ribbon graph that is a thin neighborhood of the planar diagram as
described in Figure~\ref{snake}, where the boundary connection at every vertex is
of type (A) in Figure~\ref{flip}. The connection of boundary curves is as Figure~\ref{strand-connection}(f) at every vertex.
We successively change boundary connections 
from type (A) to type (C) at a subset of  vertices we describe below.
With every such change, the number of boundary components of the corresponding ribbon graph reduces by $2$, and hence the genus increases by $1$. 
We start by changing the boundary connections for the vertices in the subgraph in 
box (X).
For  $n$ odd,  we change the boundary connection at 
vertices $v_1$ and $v_2$ in Figure~\ref{leftshade}(odd), 
and for $n$ even,  at 
vertices $v_1$, $v_2$ and $v_3$ in Figure~\ref{leftshade}(even). 
The checkerboard coloring in Figure~\ref{leftshade} indicates that the boundary curves of the 
regions of the same shading are connected. 



\begin{figure}[ht]
\begin{minipage}[b]{0.26\linewidth}
\centering
\includegraphics[scale=.25]{leftshade}
\caption{Shading  (X) }
\label{leftshade}
\end{minipage}\hskip .5cm
%
\begin{minipage}[b]{0.3\linewidth}
\centering
\includegraphics[scale=.28]{middle}
\caption{Shading  (Y) }
\label{middle}
\end{minipage}
%
\begin{minipage}[b]{0.375\linewidth}
\centering
{\includegraphics[scale=.19]{induction16.eps}
\caption{Shading (Z)}}
\label{induction16}
\end{minipage}
\end{figure}



Next we proceed to box (Y) inductively. In Figure~\ref{middle}, after the changes of the boundary connections at vertices $v_i$ and $v_{i+1}$  in this order,
the boundary curves are connected 
for the curves of the regions of the same shading in Figure~\ref{middle}.
Note that the boundary curves of the four regions (a) through (d) in the figure 
belong to distinct components. Hence the connection changes at the vertices 
$v_{i+2}$ and $v_{i+3}$ in this order 
connects the curves (a) and (c), (b) and (d) to those two curves 
corresponding to the two shadings, respectively. 
Inductively, by changing boundary connections in all thickened 
vertices in Figure~\ref{snake} box (Y), all curves bounding the regions in box (Y) are connected to two boundary components. The two components are indicated by the checkerboard shading.


We complete the induction in box (Z) as indicated in Figure~\ref{induction16}.
The last sequences of vertices where the  boundary connections
are changed  from type (A) to (C) are 
depicted in the figure for each case (up) and (down) of Figure~\ref{rightbox}. 
 \end{proof}



\begin{proposition}\label{oddhalfgrprop}
For any  integer $n>1$,
 there exists a graph
$\Gamma$ of $2n+1$ vertices with $\gr(\Gamma)=[0, n ]$.
\end{proposition}
\begin{proof}
This follows from Proposition~\ref{halfgrprop} and Lemma~\ref{higherlem}.
\end{proof}


Next, we find the genus range of a  family  
of  graphs
called the tangled cords. Furthermore, in view of 
Problem~\ref{MainProblem}, 
we prove that for all odd $n$ the maximum 
genus range 
$\{ \lfloor \frac{n-1}{2}\rfloor , \lfloor \frac{n+1}{2}\rfloor\}$ is achieved by the tangled cord with $n$ vertices.
The analysis of the genus range in this case uses a technique of  {addition}  and {removal} of a vertex, described in Section~\ref{AdditionRemovalVertexsection}.

\begin{definition}\rm{A {\it tangled cord} {\cite{BDJMS}}
with $n$ vertices and $2n$ edges, denoted $T_n$,  is a special type of  graphs of the form illustrated in Figure~\ref{TC}.}
\end{definition}

The graph $T_n$ corresponds to the  double-occurrence word $$ 1213243 \cdots (n-1)(n-2)n(n-1)n . $$
Specifically, $T_1, T_2$ and $T_3$ correspond to $11$, $1212$, and $121323$ respectively,
and the  double-occurrence word of 
$T_{n+1}$ is obtained from the  double-occurrence word of 
  $T_{n}$ by replacing the last letter $(n)$ by
the subword $(n+1)n(n+1)$. Figure~\ref{TC} shows the structure of the tangled cord.
For vertices and edges of $T_n$, we establish the following notation for the rest of the section.
The edges of $T_n$ are enumerated as $e_1, \ldots, e_{2n}$ as they are encountered by the transverse path given by the  double-occurrence word, in this order. 
The adjacent edges to each vertex are listed below, in the cyclic order around the vertex,  as follows. 
\[\begin{tabular}{l}
$v_1:\ e_1,e_3, e_{2n}, e_2$ \\
$v_2:\ e_1,e_5, e_2, e_4$ \\
$v_i:\ e_{2(i-1)}, e_{2i}, e_{2(i-2)+1}, e_{2i+1}\mbox{ for }i\neq 1,2,n-1,n$\\
$v_{n-1}:\ e_{2(n-2)}, e_{2n-2}, e_{2(n-3)+1}, e_{2n-1}$\\
$v_n:\ e_{2n}, e_{2n-2}, e_{2n-1}, e_{2n-3}$
\end{tabular}\]
By construction, $T_{n+1}$ is obtained from $T_n$ by addition of a vertex $v_{n+1}$ by crossing $e_{2n-1}$ and $e_{2n}$ 
 as in Figure~\ref{TC}, with the cyclic order  $e_{2n+1}, e_{2n-1},  e_{2n}, e_{2n-2}$ at $v_{n+1}$. 

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{tangled-cord-induction.eps} 
\caption{Tangled cord $T_n$}
\label{TC}
\end{center}
\end{figure}



The tangled cord $T_n$ was introduced in \cite{BDJMS} as a graph that provided a tight upper bound on the number of 
Hamiltonian polygonal paths (paths in which consecutive edges are neighbors with respect to their common incidence vertex visiting every vertex exactly once) over all  graphs of the same number of vertices.


We prove that  for each $T_n$, if $F$ is a  ribbon graph for $T_n$ then it has either 1 or 3 boundary components 
(if $n$ is odd) or it has 2 or 4 boundary components (if $n$ is even). 
First we prove the following lemma:
\begin{lemma}\label{TC-bound}
Let $F$ be a  ribbon graph for $T_n$ ($n\ge 2$) and suppose $B$ is the
 set of boundary components that trace edges $e_{2n-1}$ and $e_{2n}$. 
 Then every edge of $T_n$ is traced by a curve in $B$. 
\end{lemma}

\begin{proof} We use the following notation: for any set $E$ of edges, let $B(E)$ be the set of boundary components 
of the  ribbon graph $F$ that trace at least one edge in $E$.  So $B$ 
in the statement is written as $B(\{e_{2n-1},e_{2n}\})$. Observe that $B$ has at most four elements as there are at most four boundary components tracing two edges.
Edges $e_{2n-1}$ and $e_{2n}$ in $T_n$  are not neighbors, but they are consecutive edges of the transverse path defining $T_n$. Hence all boundary components tracing $e_{2n-1}$ and $e_{2n}$ (which are at most four) must trace their neighboring edges $e_{2n-2}$ and $e_{2n-3}$ (see Figure~\ref{flip}(A) or (C)). Therefore 
$B(\{e_{2n},e_{2n-1},e_{2n-2},e_{2n-3}\})= B$. 
 But then edges $e_{2n-1}$ and $e_{2n-2}$ are consecutive edges of the transverse path at vertex $v_{n-1}$ and so, all boundary components that trace $e_{2n-1}$ and $e_{2n-2}$ must also trace their neighboring edges at 
 $v_{n-1}$, that is,  edges $e_{2n-4}$ and $e_{2n-5}$. So $B(\{e_{2n},\ldots, e_{2n-5}\})=B$.
 
 \begin{sloppypar}
 Inductively, if $B(\{e_{2n},\ldots,e_{2i},e_{2i-1}\})=B$, then all edges incident to vertices $v_n, v_{n-1},\ldots,v_{i+1}$
 ($i\ge 2$) are traced with boundary components from $B$. The edges $e_{2i+1}$ and $e_{2i}$ are not neighbors
 and are both 
  incident to $v_i$, therefore the boundary components that trace $e_{2i+1}$ and $e_{2i}$, also trace 
 $e_{2i-2}$ and $e_{2i-3}$. Hence $B(\{e_{2n},e_{2n-1},\ldots, e_{2i-2},e_{2i-3}\})=B$. If $i=2$ we obtain that 
 $B(E)=B$ where $E$ is the set of all edges of $T_n$.
 \end{sloppypar}
 \end{proof}
 
 As a consequence of Lemma~\ref{TC-bound}, and the fact that the parity of the number of boundary components of the  ribbon graph must match the parity of the vertices from Lemma~\ref{Eulerlem}, 
  we have that if $n$ is even then any  ribbon graph of $T_n$ has 2 or 4
 boundary components, and if $n$ is odd, then any  ribbon graph of $T_n$ has 1 or 3 boundary components. In the following we observe that all these situations appear.

 
  \begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{TC-4strands.eps}
\caption{Connections of four boundary components in $T_n$}
\label{TC-4strands}
\end{center}
\end{figure}

 \begin{lemma}\label{TC-three}
  For every odd number $n>2$ there is a  ribbon graph of $T_n$ with three  boundary components.
 \end{lemma}
 
\begin{proof} 
This lemma is a corollary of 
Lemma~\ref{notnnlem} (and its proof) 
where it is observed that for every  graph there is a ribbon graph with more than one boundary component. 
\end{proof}



\begin{lemma}\label{TC-four}
For every odd number $n>2$,  there is a   ribbon graph $F$ 
of $T_n$ 
with a single boundary component tracing edges $e_{2n}$
and $e_{2n-1}$  whose global connection is as in Figure~\ref{add-vertex-strands}(f).
\end{lemma}

\begin{proof}
Since $n$ is odd, the number of boundary components are either 1 or 3. 
The global connection of the boundary component in Figure~\ref{add-vertex-strands}(f) implies that the four 
possible boundary components tracing edges $e_{2n}$ and $e_{2n-1}$ (indicated in 
Figure~\ref{TC-4strands}(a)
with 1 through 4)  are connected such that 1 is connected to 2, 2 connected to 3.
If $3$ is connected to $1$, there would be two boundary components, hence 3 must be connected to 4, and back to 1. 
Therefore we only need to show that there is a  ribbon graph where 1 is connected to 2  and 2 to 3. 
Suppose a  ribbon graph 
corresponding to a fixed planar diagram  in Figure~\ref{TC-4strands}(a)
has boundary curves connected as type (A) of Figure~\ref{flip}
at vertices $v_n, v_{n-1}, \ldots, v_5$ and also at vertex $v_1$. Then  following the indicated arrows 
in Figure~\ref{TC-4strands}(a)  the boundary curves visit vertices:
$$
\begin{array}{lllllll}
v_n & v_{n-2} & v_{n-3} & v_{n-5} & v_{n-6} & v_{n-8}  & v_{n-9}  \ldots 
\mbox{by following boundary curve 1}\qquad(*)\\
v_n & v_{n-1} & v_{n-3} & v_{n-4} & v_{n-6} & v_{n-7} & v_{n-9}  \ldots 
\mbox{by following boundary curve 2}\qquad(**)
\end{array}
$$

It follows that the two curves  ``meet" at every other vertex they visit 
(with indices changing in gaps of 3), but if the two curves ``meet'' at $v_i$,  one of the curves  traces edge $e_{2i}$
and the other traces $e_{2i+1}$. There are three possibilities for the vertex of the 
smallest index  (greater than 2) for $(*)$ and $(**)$ to ``meet":
 at vertex $v_3$, vertex $v_4$ and at vertex $v_5$ respectively. 
 These situations are depicted in Figure~\ref{TC-4strands}(b--d, respectively) where the blue 
 component indicates (*) and the red indicates (**). 
 
The curves ``meet" at vertex $v_3$ when  $n=6k+3$ 
 (Figure~\ref{TC-4strands}(b)), in which case we consider the ribbon graph where the boundary curves 
 are connected 
  at vertex $v_2$ in  type (C) in Figure~\ref{flip}, and at all other vertices the connections are of type (A). 
The curves ``meet" at vertex $v_4$ when $n=6k+1$
 (Figure~\ref{TC-4strands}(c)),  
 in which case we consider the ribbon graph where the boundary curves 
 are connected 
  at vertex $v_4$ in  type (C), and at all other vertices the connections are of type (A).   
  The curves ``meet" at vertex $v_5$ when $n=6k+5$
 (Figure~\ref{TC-4strands}(d)), 
  in which case we consider the ribbon graph where the boundary curves 
 are connected 
  at vertex $v_2$ and $v_3$ in  type (C), and at all other vertices the connections are of type (A).
  In all three cases we note that: (i)  the (blue) boundary curve  1  that traces $e_3$ to $v_1$ 
and then $e_{2n}$, continues to ``join" with boundary curve 2 and (ii) the (red)
 boundary curve 2 that traces the even edges 
$e_6, e_8, e_{10}, \ldots,  e_{2n-2}$, and then $e_{2n-1}$ ``joins" with boundary curve 3 (Figure~\ref{TC-4strands}(a)). Since in all three cases  situations (i) and (ii)  appear, the
  global connection of the boundary components at edges $e_{2n-1}$ and $e_{2n}$ are the same as in 
   Figure~\ref{add-vertex-strands}(f).
\end{proof}

 The following proposition gives the final result about the genus range of $T_n$.
 

\begin{proposition}\label{TCthm} 
Let $T_n$ be the tangled cord with $n=2k$  or $2k-1$ vertices. Then
$ \gr(T_n)=[k-1, k]$. 
\end{proposition}



\begin{proof} 
Recall that there are at most 4 boundary components by Lemma~\ref{TC-bound}. 
By Lemmas ~\ref{TC-three},~\ref{TC-four}  for every odd $n$, there is a  ribbon graph for $T_n$ with one boundary component and there is a  ribbon graph for $T_n$ with three boundary components. We  need to prove,
for $n$ even, that there are ribbon graphs with  2 and 4 boundary components. 
 The graph $T_{n+1}$ is obtained from $T_n$ by vertex addition by crossing $e_{2n-1}$ and $e_{2n}$. 
 Suppose $n\ge 3$ is odd. Then $T_n$ has  ribbon graphs with one and three components. 
By Lemma~\ref{lem:add-vertex}(iii) by adding vertex $v_{n+1}$ through crossing $e_{2n-1}$ and 
$e_{2n}$ the three-component  ribbon graph for $T_n$ becomes a 
ribbon graph with two boundary components 
for $T_{n+1}$.
By Lemma~\ref{TC-four} there is a   ribbon graph for $T_n$ with a single boundary component, in which the global boundary connection traces edges $e_{2n-1}$ and $e_{2n}$ as  in Figure~\ref{add-vertex-strands}(f). 
Then after  adding vertex $v_{n+1}$ by crossing $e_{2n-1}$ and 
$e_{2n}$, this  ribbon graph becomes a ribbon graph
with four boundary components 
for $T_{n+1}$. By Lemma~\ref{Eulerlem}  the result follows.
\end{proof}





%%%%%%%%%%%%%%%
\section{Towards Characterizing Genus Ranges }\label{Characterize}
%%%%%%%%%%%%%


In this section we state and prove the main theorem
on genus ranges of transversely connected 4-regular rigid vertex graphs. % 
First we set the following notation. 

\begin{definition} {\rm We define the {\it consecutive power set} of $\{0, 1, \ldots, n\}$ for a positive integer $n$,
denoted by ${\cal CP}(n)$, to be the set of all consecutive positive integers:
${\cal CP}(n) = \{ \, [ a, b ] \, | \, 0 \leq a \leq b \leq n \}$. }
\end{definition}



\begin{corollary}\label{cplem} 
For any $n \in \N$, we have $\GR_{2n-1}, \GR_{2n} \subset {\cal CP}(n)$. 
\end{corollary}
\begin{proof}
This follows from Lemma~\ref{conseclem}, and Lemma~\ref{Eulerlem} since $b(F)\geq 0$. 
\end{proof}




To describe the 
genus  
  ranges we can realize, we define the following integer sequence.
For a positive integer $n$, define
$\displaystyle K_n=\left\lfloor \frac{n+1}{7} \right\rfloor$,
$\displaystyle L_n=\left\lfloor \frac{n - 7 K_n +1}{3} \right\rfloor$, 
and $\psi_n= 3 K_n + L_n $.
For $n=100$, for example, $K_n=14$, $L_n=1$ and $\psi_n=43$. 
These numbers allow us to state the main theorem in the paper. 


\begin{theorem}\label{mainthm} {\ }  

\noindent
{\rm (i)} For  any  $n>1$,  $n\in \N$,
$ \GR_{2n} $ contains the set    
${\cal CP}(n)\setminus \{ [h,h]\, | \, \psi_{2n} < h \leq n \}$.  

\noindent
{\rm (ii)} For any $n\in \N$, 
$ \GR_{2n-1}$ contains the set  
 ${\cal CP}(n) \setminus \{ [0, n], [h,h] \, | \,  \psi_{2n-1} < h \leq n\}$.  


\noindent
{\rm (iii)} For   any $n\in \N$,  
$ [0, n],  [n,n] \notin \GR_{2n-1}$. 
\end{theorem}



\begin{proof}
The  part (iii) is a restatement of Lemmas~\ref{fullrangelem} and~\ref{notnnlem}. We show (i) and (ii) by induction and constructions.
Computer calculations in Table~\ref{CalculationsTable} show that the statements hold for $n=1,2,3$ for $\GR_{2n-1}$ and 
$n=2,3$ for 
$\GR_{2n}$. 

First we focus on sets $[a,b]$ with $a < b$. 
Assume   for induction that $\GR_{2k-1}$ contains 
all sets $[a, b] \in {\cal CP}(k)$, where $a <b \leq k$, excluding $[0,k]$.
By Lemma~\ref{higherlem},  
all these sets are   contained in  $\GR_{2k}$. 
Proposition~\ref{halfgrprop} implies that  $[0, k]$ is contained in $\GR_{2k}$ and so is in $\GR_{2k+1}$. 
Hence all sets $[a, b] \in {\cal CP}(k)$, where $a <b \leq k$ for $n \leq k$, are contained in  $\GR_{2k}$
and    $\GR_{2k+1}$.



Assume next  that  $\GR_{2k}$ contains all sets $[a, b] \in {\cal CP}(k)$, where $a <b \leq k$, 
and also that $\GR_{2k-1}$ contains all sets $[a, b] \in {\cal CP}(k)$, where $a <b \leq k$, excluding $[0,k]$.
By Lemma~\ref{higherlem},  all $[a, b] \in {\cal CP}(k)$, where $a <b \leq k$, are contained in $\GR_{2k+1}$. 
We show that $\GR_{2k+1}$ contains  all $[a, b] \in {\cal CP}(k+1)$, where $a <b \leq k+1$, excluding $[0,k+1]$.
Among these wanted, the following have not been covered by the induction assumption:
$ [h, k+1] $ for $h=1, \ldots, k$ and $[0, k]$. 
There is a graph with $2k+1$ vertices and genus range $[0, k]$
by Proposition~\ref{oddhalfgrprop}. 
Thus we construct a graph $\Gamma$ with $|\Gamma|=2k+1$ and $\gr(\Gamma)=[h, k+1]$ for $h=1, \ldots, k$.
Let $T_{2h+1}$ be the tangled cord of size $2h+1$, which has genus range $[h, h+1]$ by Proposition~\ref{TCthm}. 
Let $F$ be a ribbon graph of $T_{2h+1}$ with genus $h$, and hence with $3$ boundary components. 
We claim that there is an edge that is traced by a single component. Assume otherwise, that every edge is traced by distinct components. Since  $4$ boundary curves meet at every vertex, and there are $3$ boundary components, 
at least two curves 
at each  vertex belong to the same component.


 In  Figure~\ref{strand-connection},
there are two possibilities with $3$ boundary components at the top row, cases (e) and (h). 
Case (e) contains an edge traced by a single component, hence it is excluded by assumption. 
 After the connection change (Figure~\ref{strand-connection} (h) bottom), the total number of boundary components
stays as $3$. A similar inspection shows that if both diagonal components belong to the same components (and 
$2$ components meet at the vertex, Figure~\ref{strand-connection} (j)), then the connection change would separate these components into $4$ components, 
which is impossible with $T_{2h+1}$
by Proposition~\ref{TCthm}. 
Therefore if every edge is traced by distinct components, then at every vertex the situation must be 
as in Figure~\ref{strand-connection} (h). But  then, a connection change at 
any  vertex does not change the number of components $3$, which again contradicts Proposition~\ref{TCthm}
that the genus range of  $T_{2h+1}$ is not a singleton. 
Hence there exists an edge $e$ that is traced by a single component. 


In Lemma~\ref{plus1lem}, let $\Gamma=T_{2h+1}$ 
with the choice of an edge $e$ that is traced by a single component for some ribbon graph $F$ as found above. 
By (the proof of) Lemma~\ref{plus1lem}, 
the genus range of the graph $\Gamma'$ obtained by connecting a pretzel along 
the edge $e$ from  $\Gamma$ 
 has genus range $[h, h+2]$ and has size $2h+3$. The edge connection
of $\Gamma_0$  that gives rise to
the genus $h$ for $\Gamma'$ is as depicted in Figure~\ref{tref}(E). 
Hence either of the edges connecting $\Gamma$ and $\Gamma_0$ is traced by a single boundary component 
for the ribbon graph resulted from these surfaces for $\Gamma$ and $\Gamma_0$.
Inductively, by taking this graph $\Gamma'$ as a new $\Gamma$,  and by repeating  this process
$(k-h)$ times, 
we obtain a graph with genus range $[h, h+1+(k-h)]=[h, k+1]$ and size 
$(2h+1) + 2(k-h)=2k+1$ as desired. 

We analyze the case $[a,a]$. 
Computer calculation shows that 
there is a unique graph $\Gamma_6$
 with genus range $[3,3]$
 among all 6 vertex graphs.
 The graph $\Gamma_6$ is   represented by $123245153646$.
Let $\Gamma (K, L)$ 
be the graph obtained by taking cross sums 
of $K$ copies of $\Gamma_6$ and $L$ copies of $\Gamma_0$ 
(represented by the word $1212$). 
Then the number of vertices of $\Gamma (K, L)$ is $7 K + 3 L -1$.
Its genus range is $[ \psi, \psi]$ where $\psi= 3K + L$. 
The number of vertices of the graph $\Gamma (K-1, L+2) $ 
is one less than that of $\Gamma (K, L)$ and its genus range 
is $[ \psi -1, \psi -1]$. 
If $K=0$, the  number of vertices of the graph $\Gamma (0, L-1) $ 
is two  less than that of $\Gamma (0, L)$ and its genus range 
is $[ \psi -1, \psi -1]$. 
For $n<6$, the statement follows from computer calculation (Table 1).
For   $n\geq 6$, the genus range of the graph $\Gamma (K_n, L_n)$
is $[\psi_n, \psi_n]$, and theorem follows by considering 
$\Gamma (K,L)$ with $K \leq K_n$ as above and applying 
Corollary~\ref{higherlem}.
\end{proof}


  \begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{thm.eps}
\caption{Diagram representing the conjecture}
\label{thm}
\end{center}
\end{figure}


\begin{conjecture}
{\rm
For any $m \in \N$, 
there is an integer $\Psi_m\ge \psi_m$ such that 
$$\begin{array}{lll}
\GR_{2n} &=& {\cal CP}(n) \setminus \{ \, [h,h]\, | \, \Psi_{2n} < h \leq n \, \} , \\
\GR_{2n-1} &=& {\cal CP}(n) \setminus \{ \, [0, n], [h,h]\, | \, \Psi_{2n-1} < h \leq n \, \}.  
\end{array} $$}
\end{conjecture}

This means that there is no gap along the diagonal (see Figure~\ref{thm}). 
For small values of $m\leq 20$, the conjecture holds with $\Psi_m=\psi_m$  for 
$m=1, \ldots, 7, 9, 13$. At this time we are not able to determine if 
$[5,5]$ is in $\GR_m$ for $m=10, 11$, $[6,6]$ for $m=12$,  $[7,7]$ for $m=14,15$, 
$[8,8]$ for $m=16, 17, 18$, and $[9,9]$ for $m=18, 19$.
The conjecture is true if there is only one unknown entry, and therefore, 
the conjecture holds for all $m\leq 20$  except $m=18$, and $m=18$ is the smallest number for which 
we do not know if the conjecture holds. If one finds $[8,8] \notin \GR_{18}$ but $[9,9]\in  \GR_{18}$,
then this will provide a counterexample. 
For $n=100$, for example, we do not know if $[h,h] \in \GR_{100}$ for 
$h=43,  \ldots, 50$. 
We know that $[4,4]$ is not in $\GR_8$ only by 
computer calculations in Table~\ref{CalculationsTable}
searching through all  graphs with 8 vertices.  


The situation for graphs with $n$ vertices 
 is depicted in Figure~\ref{thm}. Dots with the coordinates $(a,b)$ represents the genus range $[a,b]$.
The black dots represent that we have proved that there exists a graph with 
the corresponding genus range.
Unmarked lattice points represent that there is no graph with the corresponding genus range due to 
the Euler characteristic formula. The white dots represent that we have proved, in this paper, that there are no graphs
with such genus ranges. The red dots with question marks represent that these upper diagonal ranges remain 
unknown, beyond the number $\psi_n$ we provided. 




\section{Concluding Remarks}\label{ConclSec}

For 
transversely connected 
4-regular  rigid vertex graphs, we considered 
 the orientable genus range, that are genera of cellular embeddings.
Some ranges are realized by using specific families of graphs, and others by some operations applied on graphs of smaller sizes. 
A few ranges are shown to be not realized as genus range. 
We identify particular intervals and singletons $[h,h]$ that are unknown to be genus ranges. An interesting open question is whether these in fact can be realized.

\begin{figure}[h]
\begin{center}
  \includegraphics[scale=0.75]{histogram.eps} 
\end{center}
\vspace{-0.5cm}
\caption{Histogram of genus range distributions for the number of  graphs graphs with 7 and 8 vertices, with a given genus range }
\label{fig:genus_ranges_7_8}
\end{figure}




In Figure~\ref{fig:genus_ranges_7_8}(right), we note that there are only 13 graphs  among 65346 graphs 
of 8 vertices with genus range $[0, 4]$. In Proposition~\ref{halfgrprop},
we constructed graphs with $2n$ vertices with genus range $[0,n]$, and these graphs seem to be very rare.
Also we notice that among 7 vertex graphs, there are only 2 graphs  with genus range $[3,3]$. 
It is a curious fact that certain types of genus rages are very rare, and some are numerous. 
It may be of interest to determine the distributions of genus ranges. 




We conclude with comments on possible relations and applications to the studies on DNA assembly.
A mathematical model using 4-regular rigid vertex  graphs for DNA recombination processes was proposed and studied in
\cite{Angeleska2009,Angeleska2007,BDJMS}. 
The molecular structure in space at the exact moment of recombination is modeled by assembly graphs, and the assembled gene is modeled by {\it Hamiltonian polygonal paths},  paths that make  
``$90^\circ$ turn" 
   at every rigid vertex, and visit every vertex exactly once.
These polygonal paths  
  have been also studied in graph theory as A-trails (for example, \cite{ABJ}).
In \cite{BDJMS}, it was proved that the tangled cord,
which achieves the maximal genus range for at least the graphs with odd number of vertices,  
has the largest number of Hamiltonian polygonal paths among all
assembly graphs of the same number of vertices.
 If one follows a boundary curve of a  ribbon graph 
 at every vertex (see Figure~\ref{flip}), 
  the consecutive edges traced by the boundary curve must be neighbors, so they form a polygonal path. 
Thus it is expected that smaller numbers of boundary components   contribute to larger numbers of Hamiltonian 
polygonal paths. 
However, an explicit  relationship between the genus range and the number of 
Hamiltonian polygonal paths is still unknown.  


\subsection*{Acknowledgements}
We wish to thank F. Din-Houn Lau and Kylash Rajendran, Erica Flapan, Mauro Mauricio and Julian Gibbons for insightful discussions.   
We also thank Ryan Arredondo for pointing out errors in an earlier version and Paul Kainen for useful references and comments. 
DB is supported in part by EPSRC Grants EP/H0313671, EP/G0395851 and EP/J1075308, and thanks the LMS and the Leverhulme Research Grant RP2013-K-017. KV was supported by EP/G0395851 to DB.   This research was partially
supported by grants 
NSF CCF-1117254,
and NIH 1R01GM109459.





\begin{thebibliography}{10}


\bibitem{ABJ}
L.D. Andersen, A.~Bouchet, and  B. Jackson.
Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus.
{\it Journal of Combinatorial Theory, Series B}  66:232--246, 1996. 

\bibitem{Angeleska2009} A. Angeleska, N. Jonoska, and M. Saito. DNA recombination through assembly graphs. {\it Discrete Applied Mathematics}
157:3020--3037,  2009.

\bibitem{Angeleska2007} A. Angeleska, N. Jonoska, M. Saito, L.F. Landweber.
 RNA-guided DNA assembly.
 {\it  Journal of Theoretical Biology} 248(4):706--720,  2007.


\bibitem{Dror}
D. Bar-Natan. { On the Vassiliev knot invariants.}
{\it Topology} 34(2):423--472,  1995. 


\bibitem{BDK} K. Bhandari, H.A. Dye, and L.H. Kauffman.
 Lower bounds on virtual crossing number and
 minimal surface genus.
% in: 
{\it The Mathematics of Knots (1)}, Contributions in Mathematical and Computational Sciences,
B. Markus, V. Denis (Eds), Springer 31--43,  2011. 

\bibitem{BDJMS} J. Burns, E. Dolzhenko, N. Jonoska, T. Muche, M. Saito.
Polygonal
Hamiltonian paths in rigid 4-regular graphs and DNA assembly.
{\it  Discrete Applied Mathematics} 161:1378--1394,  2011.

\bibitem{CE1}
G. Cairns and D.M. Elton. 
{ The planarity problem for signed Gauss words}.
{\it Journal of Knot Theory and its Ramifications}
{ 2}:359--367,  2011.

\bibitem{CE2}
G. Cairns and  D.M. Elton.
{ The planarity problem II}.
{\it Journal of Knot Theory and its Ramification}
{ 5} :137--144,  2011.

\bibitem{Carter}
J. S. Carter. { Classifying immersed curves.} 
{\it Proc. Amer. Math. Soc.} 111(1):281--287, 1991.

\bibitem{JSC}
J. S. Carter. personal communication, 2011.



\bibitem{Sergei}
S.  Chmutov. { Generalized duality for graphs on surfaces and the signed Bollob�s-Riordan polynomial.}
{\it  J. Combin. Theory Ser. B} 99(3):617--638,  2009.
 
 \bibitem{Duke1966} R.A. Duke. 
  The genus, regional number, and Betti number of a graph.
  {\it  Canad. J. Math.} 18:817--822,   1966.

\bibitem{DK} H. Dye and  L. H.  Kauffman.
{Minimal surface representations of virtual knots and links.}
{\it  Algebr. Geom. Topol.}
 5:509--535,  2005.


\bibitem{gross-book}
J. L. Gross and  T. W. Tucker.
{\it  Topological graph theory.} Dover Publications, Inc., Mineola, NY, 2001.

\bibitem{Jonoska2002} N. Jonoska and  M. Saito.
{ Boundary components of thickened graphs.}
{\it  Lecture Notes in Computer Science}  2340:70--81,  1960.


\bibitem{Kauff}
L. H. Kauffman.  {\it  Knots and physics, third edition.}
 Series on Knots and Everything, 1, World Scientific Publishing Co., Inc., River Edge, NJ, 2001.


\bibitem{MoharThomassenBook} B. Mohar and  C. Thomassen.
{\it  Graphs on Surfaces.}
The Johns Hopkins University Press, Baltimore, 2001. 



\bibitem{SS}
M. \v Skoviera and  J. \v Sir\'a\v n.
Oriented relative embeddings of graphs.
{\it Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985),
Zastos. Mat.} 19:589--597,    1987. 

\end{thebibliography}




\end{document}