---
abstract: 'We investigate the [*toroidal expanse*]{} of an embedded graph $G$, that is, the size of the largest toroidal grid contained in $G$ as a minor. In the course of this work we introduce a new embedding density parameter, the [*stretch*]{} of an embedded graph $G$, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar [*crossing number*]{} of $G$. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface-embedded graph with bounded maximum degree.'
author:
- 'Markus Chimani[^1]'
- 'Petr Hliněný [^2]'
- 'Gelasio Salazar[^3]'
title: 'Toroidal Grid Minors and Stretch in Embedded Graphs[^4] '
---

[**Keywords:**]{} Graph embeddings, compact surfaces, face-width, edge-width, toroidal grid, crossing number, stretch

[**AMS 2010 Subject Classification:**]{} 05C10, 05C62, 05C83, 05C85, 57M15, 68R10

Introduction {#sec:intro}
============

In their development of the Graph Minors theory towards the proof of Wagner’s Conjecture [@RoSeGMXX], Robertson and Seymour made extensive use of surface embeddings of graphs. Robertson and Seymour introduced parameters that measure the density of an embedding, and established results that are not only central to the Graph Minors theory, but are also of independent interest. We recall that the [*face-width*]{} $\fw(G)$ of a graph $G$ embedded in a surface $\Sigma$ is the smallest $r$ such that $\Sigma$ contains a noncontractible closed curve (a [*loop*]{}) that intersects $G$ in $r$ points.

\[thm:fw-minor\] For any graph $H$ embedded on a surface $\Sigma$, there exists a constant $c:=c(H)$ such that every graph $G$ that embeds in $\Sigma$ with face-width at least $c$ contains $H$ as a minor.

This theorem, and other related results, spurred great interest in understanding which structures are forced by imposing density conditions on graph embeddings. For instance, Thomassen [@Th94] and Yu [@Yu97] proved the existence of spanning trees with bounded degree for graphs embedded with large enough face-width. In the same paper, Yu showed that under strong enough connectivity conditions, $G$ is Hamiltonian if $G$ is a triangulation.

Large enough density, in the form of edge-width, also guarantees several nice coloring properties. We recall that the [*edge-width*]{} $\ew(G)$ of an embedded graph $G$ is the length of a shortest noncontractible cycle in $G$. Fisk and Mohar [@FM94] proved that there is a universal constant $c$ such that every graph $G$ embedded in a surface of Euler genus $g >0$ with edge-width at least $c\log{g}$ is $6$-colorable. Thomassen [@Th93] proved that larger (namely $2^{14g+6}$) edge-width guarantees $5$-colorability. More recently, DeVos, Kawarabayashi, and Mohar [@DKM08] proved that large enough edge-width actually guarantees $5$-choosability.

In a direction closer to our current interest, Fiedler et al. [@FHRR95] proved that if $G$ is embedded with face-width $r$, then it has $\floor{r/2}$ pairwise disjoint contractible cycles, all bounding discs containing a particular face. Brunet, Mohar, and Richter [@BMR96] showed that such a $G$ contains at least $\floor{(r-1)/2}$ pairwise disjoint, pairwise homotopic, non-separating (in $\Sigma$) cycles, and at least $\floor{(r-1)/8} -1$ pairwise disjoint, pairwise homotopic, separating, noncontractible cycles. We remark that throughout this paper, “homotopic” refers to “freely homotopic” (that is, not to “fixed point homotopic”).

For the particular case in which the host surface is the torus, Schrijver [@Sc93] unveiled a beautiful connection with the geometry of numbers and proved that $G$ has at least $\floor{3r/4}$ pairwise disjoint noncontractible cycles, and proved that the factor $3/4$ is best possible.

The [*toroidal $p \times q\>$-grid*]{} is the Cartesian product $C_p\Box C_q$ of the cycles of sizes $p$ and $q$. See Figure \[fig:torgrid\]. Using results and techniques from [@Sc93], de Graaf and Schrijver [@dS94] showed the following:

\[thm:deGS\] Let $G$ be a graph embedded in the torus with face-width $\fw(G)=r\ge 5$. Then $G$ contains the toroidal $\floor{2r/3} \times \floor{2r/3}\>$-grid as a minor.

De Graaf and Schrijver also proved that $\floor{2r/3}$ is best possible, by exhibiting (for each $r\ge 3$) a graph that embeds in the torus with face-width $r$ and that does not contain a toroidal -grid as a minor. As they observe, their result shows that $c=\ceil{3m/2}$ is the smallest value that applies in (Robertson-Seymour’s) Theorem \[thm:fw-minor\] for the case of $H=C_m\Box C_m$.

Our focus: toroidal expanse, stretch, and crossing number
---------------------------------------------------------

Along the lines of the aforementioned de Graaf-Schrijver result, our aim is to investigate the largest size (meaning the number of vertices) of a toroidal grid minor contained in a graph $G$ embedded in an arbitrary orientable surface of genus greater than zero. We do not restrict ourselves to square proportions of the grid and define this parameter as follows.

\[def:texpanse\] The [*toroidal expanse*]{} of a graph $G$, denoted by $\Tex(G)$, is the largest value of $p\cdot q$ over all integers $p,q\geq3$ such that $G$ contains a toroidal $p \times q\>$-grid as a minor. If $G$ does not contain $C_3\Box C_3$ as a minor, then let $\Tex(G)=0$.

Our interest is both in the structural and the algorithmic aspects of the toroidal expanse.

The “bound of nontriviality” $p,q\geq3$ required by Definition \[def:texpanse\] is natural in the view of toroidal embeddability —the degenerate cases $C_2\Box C_q$ are planar, while $C_p\Box C_q$ has orientable genus one for all $p,q\geq3$. It is not difficult to combine results from [@BMR96] and [@dS94] to show that for each positive integer $g>0$ there is a constant $c:=c(g)$ with the following property: if $G$ embeds in the orientable surface $\Sigma_g$ of genus $g$ with face-width $r$, then $G$ contains a toroidal $c\cdot r \times c\cdot r\>$-grid as a minor; that is, $\Tex(G) = \Omega(r^2)$.

On the other hand, it is very easy to come up with a sequence of graphs $G$ embedded in a fixed surface with face-width $r$ and arbitrarily large $\Tex(G)/ r^2$: it is achieved by a natural toroidal embedding of $C_r \Box C_{q}$ for arbitrarily large $q$. This inadequacy of face-width to estimate the toroidal expanse of an embedded graph is to be expected, due to the one-dimensional character of this parameter.

To this end, we introduce a new density parameter of embedded graphs that captures the truly two-dimensional character of our problem; the [*stretch of an embedded graph*]{} in Definition \[def:stretch\]. Using this tool, we unveil our main result—a tight two-way relationship between the toroidal expanse of a graph $G$ in an orientable surface and its [*crossing number*]{} $\crg(G)$ in the plane. We furthermore provide an approximation algorithm for both these numbers under an assumption of a sufficiently dense embedding. A simplified summary of the main results follows:

\[thm:main-overview\] Let $\Sigma$ be an orientable surface of fixed genus $g>0$, and let $\Delta$ be an integer. There exist constants $r_0,c_0,c_1,c_2>0$, depending only on $g$ and $\Delta$, such that the following holds: If $G$ is a graph of maximum degree $\Delta$ embedded in $\Sigma$ with face-width at least $r_0$, then

-   $c_0\cdot\crg(G) \leq \Tex(G) \leq c_1\cdot\crg(G)$, and

-   there is a polynomial time algorithm that outputs a drawing of $G$ in the plane with at most $c_2\cdot\crg(G)$ crossings.

The density assumption that $\fw(G)\geq r_0$ is unavoidable for (a). Indeed, consider a very large planar grid plus an edge. Such a graph clearly admits a toroidal embedding with face-width $1$. By suitably placing the additional edge, such a graph would have arbitrarily large crossing number, and yet no $C_3\Box C_3$ minor. However, one could weaken this restriction a bit by considering “nonseparating” face-width instead, as we are going to do in the proof. Furthermore, we shall show later (Section \[sec:nodensity\]) how to remove the density assumption $\fw(G)\geq r_0$ completely for the algorithm (b), using additional results of [@MR2874100].

Regarding the constants $r_0,c_0,c_1,c_2$ we note that, in our proofs,

-   $r_0$ is exponential in $g$ (of order $2^g$),

-   $c_1$ is independent of $g,\Delta$, and

-   $c_2$ and $1/c_0$ are quadratic in $\Delta$ and exponential in $g$ (of order $8^g$).

The rest of this paper is structured as follows. In Section \[sec:prelims\] we present some basic terminology and results on graph drawings and embeddings, and introduce the key concept of stretch of an embedded graph. In Section \[sec:mainresults\] we give a commentated walkthrough on the lemmas and theorems leading to the proof of Theorem \[thm:main-overview\]. The exact value of the constants $r_0,c_0,c_1,c_2$ is given there as well. Some of the presented statements seem to be of independent interest, and their (often long and technical) proofs are deferred to the later sections of the paper. Final Section \[sec:concluding\] then outlines some possible extensions of the main theorem and directions for future research.

Preliminaries {#sec:prelims}
=============

We follow standard terminology of topological graph theory, see Mohar and Thomassen [@MT01] and Stillwell [@St93]. We deal with undirected multigraphs by default; so when speaking about a [*graph*]{}, we allow multiple edges and loops. The vertex set of a graph $G$ is denoted by $V(G)$, the edge set by $E(G)$, the number of vertices of $G$ (the [*size*]{}) by $|G|$, and the maximum degree by $\Delta(G)$.

In this section we lay out several concepts and basic results relevant to this work, and introduce the key new concept of stretch of an embedded graph.

Graph drawings and embeddings in surfaces {#sub:gdes}
-----------------------------------------

We recall that in a [*drawing*]{} of a graph $G$ in a surface $\Sigma$, vertices are mapped to points and edges are mapped to simple curves (arcs) such that the endpoints of an arc are the vertices of the corresponding edge; no arc contains a point that represents a non-incident vertex. For simplicity, we often make no distinction between the topological objects of a drawing (points and arcs) and their corresponding graph theoretical objects (vertices and edges). A [*crossing*]{} in a drawing is an intersection point of two edges (or a self-intersection of one edge) in a point other than a common endvertex. An [*embedding*]{} of a graph in a surface is a drawing with no edge crossings.

If we regard an embedded graph $G$ as a subset of its host surface $\Sigma$, then the connected components of $\Sigma \setminus G$ are the [*faces*]{} of the embedding. We recall that the vertices of the [ *topological dual*]{} $G^*$ of $G$ are the faces of $G$, and its edges are the edge-adjacent pairs of faces of $G$. There is a natural one-to-one correspondence between the edges of $G$ and the edges of $G^*$, and so, for an arbitrary $F\subseteq E(G)$, we denote by $F^*$ the corresponding subset of edges of $E(G^*)$. We often use lower case Greek letters (such as $\alpha, \beta, \gamma$) to denote dual cycles. The rationale behind this practice is the convenience to regard a dual cycle as a simple closed curve, often paying no attention to its graph-theoretical properties.

Let $G$ be a graph embedded in a surface $\Sigma$ of genus $g > 0$, and let $C$ be a two-sided surface-nonseparating cycle of $G$. We denote by $G\cutt C$ the graph obtained by [*cutting $G$ through $C$*]{} as follows. Let $F$ denote the set of edges not in $C$ that are incident with a vertex in $C$. Orient $C$ arbitrarily, so that $F$ gets naturally partitioned into the set $L$ of edges to the left of $C$ and the set $R$ of edges to the right of $C$. Now contract (topologically) the whole curve representing $C$ to a point-vertex $v$, to obtain a pinched surface, and then naturally split $v$ into two vertices, one incident with the edges in $L$ and another incident with the edges in $R$. The resulting graph $G\cutt C$ is thus embedded on a surface $\Sigma'$ such that $\Sigma$ results from $\Sigma'$ by adding one handle. Clearly $E(G\cutt C)=E(G)\sem E(C)$, and so for every subgraph $F\subseteq G\cutt C$ there is a unique naturally corresponding subgraph $\hat F\subseteq G$ (on the same edge set), which we call the [*lift of $F$ into $G$*]{}.

The “cutting through” operation is a form of a standard surface surgery in topological graph theory, and we shall be using it in the dual form too, as follows. Let $G$ be a graph embedded in a surface $\Sigma$ and $\gamma\subseteq G^*$ a dual cycle such that $\gamma$ is two-sided and $\Sigma$-nonseparating. Now cut the surface along $\gamma$, discarding the set $E'$ of edges of $G$ that are severed in the process. This yields an embedding of $G-E$ in a surface with two holes. Then paste two discs, one along the boundary of each hole, to get back to a compact surface. We denote the resulting embedding by $G\cutt\gamma$, and say that this is obtained by [ *cutting $G$ along $\gamma$*]{}. Note that we may equivalently define $G\cutt\gamma$ as the embedded $(G^*\cutt\gamma)^*$. Note also that $V(G\cutt\gamma)=V(G)$, and that the previous definition of a [*lift*]{} applies also to this case.

Graph crossing number
---------------------

We further look at drawings of graphs (in the plane) that allow edge crossings. To resolve ambiguity, we only consider drawings where no three edges intersect in a common point other than a vertex. The [*crossing number*]{} $\crg(G)$ of a graph $G$ is then the minimum number of edge crossings in a drawing of $G$ in the plane.

For the general lower bounds we shall derive on the crossing number of graphs we use the following results on the crossing number of toroidal grids (see [@BeR; @JS01; @KR; @RBe]).

\[thm:crossing-CpCq\] For all nonnegative integers $p$ and $q$, $\crg(C_p\Box C_q)\geq
\frac12(p-2)q$. Moreover, $\crg(C_p\Box C_q) = (p-2)q$ for $p=3,4,5$.

We note that this result already yields the easy part of Theorem \[thm:main-overview\](a):

\[cor:crossing-texp\] Let $G$ be a graph embedded on a surface. Then $\crg(G)\geq\frac1{12}\Tex(G)$.

Let $q \ge p \ge 3$ be integers that witness $\Tex(G)$ (that is, $G$ contains $C_p\Box C_q$ as a minor, and $\Tex(G)=pq$). It is known [@GS01] that if $G$ contains $H$ as a minor, and $\Delta(H)=4$, then $\crg(G)\geq\frac14\crg(H)$. We apply this bound with $H=C_p\Box C_q$. By Theorem \[thm:crossing-CpCq\], we then have for $p\in\{3,4,5\}$ that $\crg(G)\geq\frac14(p-2)q\geq\frac1{12}pq$, and for $p\geq6$ we obtain $\crg(G)\geq\frac14\cdot\frac12(p-2)q\geq\frac1{12}pq$.

Curves on surfaces and embedded cycles
--------------------------------------

For the rest of the paper, we shall exclusively focus on orientable surfaces, and for each $g\ge 0$ we let $\Sigma_g$ denote the orientable surface of genus $g$. Note that in an embedded graph, paths are simple curves and cycles are simple closed curves in the surface, and hence it makes good sense to speak about their homotopy. In particular, there are no one-sided cycles embedded in $\Sigma_g$.

If $B$ is a path or a cycle of a graph, then the [*length*]{} $\len(B)$ of $B$ is its number of edges. We recall that the [*edge-width*]{} $\ew(G)$ of an embedded graph $G$ is the length of a shortest noncontractible cycle in $G$. The [*nonseparating edge-width*]{} $\ewn(G)$ is the length of a shortest nonseparating (and hence also noncontractible) cycle in $G$. It is easy to see that the face-width $\fw(G)$ of $G$ equals one half of the edge-width of the vertex-face incidence graph of $G$. It is also an easy exercise to show that $\ew(G^*)\geq\fw(G)\geq\frac{\ew(G^*)}{\lfloor\Delta(G)/2\rfloor}$. In this paper, we are primarily interested in graphs of bounded degree. We can thus regard $\ew(G^*)$ as a suitable (easier to deal with) replacement for $\fw(G)$.

For a cycle (or an arbitrary subgraph) $C$ in a graph $G$, we call a path $P\subset G$ a [*$C$-ear*]{} if the ends $r,s$ of $P$ belong to $C$, but the rest of $P$ is disjoint from $C$. We allow $r=s$, i.e., a $C$-ear can also be a cycle. A $C$-ear $P$ is a (with respect to an orientable embedding of $G$) if the two edges of $P$ incident with the ends $r,s$ are embedded on opposite sides of $C$. The following simple technical claim is useful.

\[lem:kl2\] If $C$ is a nonseparating cycle in an embedded graph $G$ of length $\len(C)=\ewn(G)$, then all $C$-switching ears in $G$ have length at least $\frac12\ewn(G)$.

Seeking a contradiction, we suppose that there is a $C$-switching ear $D$ of length $<\frac12\ewn(G)$. The ends of $D$ on $C$ determine two subpaths $D_1,D_2\subseteq C$ (with the same ends as $D$), labeled so that $||D_1|| \le ||D_2||$. Then $D\cup D_1$ (respectively, $D\cup D_2$) is a nonseparating cycle, as witnessed by $D_2$ (respectively, $D_1$). Since $\len(D_1)\leq\frac12\len(C)$, then $$\len(D\cup D_1)\leq\len(D)+\frac12\len(C)
 <\biggl(\frac12+\frac12\biggr)\len(C)=\ewn(G)\,,$$ a contradiction.

Even though surface surgery can drastically decrease (and also increase, of course) the edge-width of an embedded graph in general, we now prove that this is not the case if we cut through a short cycle (in Lemma \[lem:cutdew\] we shall establish a surprisingly powerful extension of this simple claim).

\[lem:dew2\] Let $G$ be a graph embedded in the orientable surface $\Sigma_g$ of genus $g\geq2$, and let $C$ be a nonseparating cycle in $G$ of length $\len(C)=\ewn(G)$. Then $\ewn(G\cutt C)\geq\frac12\ewn(G)$.

Let $c_1,c_2$ be the two vertices of $G\cutt C$ that result from cutting through $C$, i.e., $\{c_1,c_2\}=V(G\cutt C)\sem V(G)$. Let $D\subseteq G\cutt C$ be a nonseparating cycle of length $\ewn(G\cutt C)$. If $D$ avoids both $c_1,c_2$, then its lift $\hat D$ in $G$ is a nonseparating cycle again, and so $\ewn(G)\leq\len(D)=\ewn(G\cutt
C)$. If $D$ hits both $c_1,c_2$ and $P\subseteq D$ is (any) one of the two subpaths with the ends $c_1,c_2$, then the lift $\hat P$ is a $C$-switching ear in $G$. Thus, by Lemma \[lem:kl2\], $$\ewn(G\cutt C)=\len(D)\geq\len(\hat P)\geq\frac12\ewn(G)\,.$$

In the remaining case $D$, up to symmetry, hits $c_1$ and avoids $c_2$. Then its lift $\hat D$ is a $C$-ear in $G$. If $\hat D$ itself is a cycle, then we are done as above. Otherwise, $\hat D\cup C\subseteq G$ is the union of three nontrivial internally disjoint paths with common ends, forming exactly three cycles $A_1,A_2,A_3\subseteq\hat D\cup C$. Since $D$ is nonseparating in $G\cutt C$, each of $A_1,A_2,A_3$ is nonseparating in $G$, and hence $\len(A_i)\geq\ewn(G)$ for $i=1,2,3$. Since every edge of $\hat D\cup C$ is in exactly two of $A_1,A_2,A_3$, we have $\len(A_1)+\len(A_2)+\len(A_3)=2\len(C)+2\len(\hat D)
    =2\ewn(G)+2\len(\hat D)$ and $\len(A_1)+\len(A_2)+\len(A_3)\geq3\ewn(G)$, from which we get $$\ewn(G\cutt C)=\len(D)=\len(\hat D)\geq\frac12\ewn(G)\,.\tag*{\qedhere}$$

Many arguments in our paper exploit the mutual position of two graph cycles in a surface. In topology, the [*geometric intersection number*]{}[^5] $i(\alpha,\beta)$ of two (simple) closed curves $\alpha,\beta$ in a surface is defined as $\min\{ \alpha'\cap \beta'\}$, where the minimum is taken over all pairs $(\alpha',\beta')$ such that $\alpha'$ (respectively, $\beta'$) is homotopic to $\alpha$ (respectively, $\beta$). For our purposes, however, we prefer the following slightly adjusted discrete view of this concept. Let $A\not=B$ be cycles of a graph embedded in a surface $\Sigma$. Let $P\subseteq A\cap B$ be a connected component of the graph intersection $A\cap B$ (a path or a single vertex), and let $f_A,f_A'\in E(A)$ (respectively, $f_B,f_B'\in E(B)$) be the edges immediately preceding and succeeding $P$ in $A$ (respectively, $B$). See Figure \[fig:defineleap\]. Then $P$ is called a [*leap of A,B*]{} if there is a sufficiently small open neighborhood $\Omega$ of $P$ in $\Sigma$ such that the mentioned edges meet the boundary of $\Omega$ in this cyclic order; $f_A,f_B,f_A',f_B'$ (i.e., $A$ and $B$ [*meet transversely in $P$*]{}). Note that $A\cap B$ may contain other components besides $P$ that are not leaps.

\[def:leaping\] Two cycles $A,B$ of an embedded graph are in a [*$k$-leap position*]{} (or simply [*$k$-leaping*]{}), if their intersection $A\cap B$ has exactly $k$ connected components that are leaps of $A,B$. If $k$ is odd, then we say that $A,B$ are in an [*odd-leap position*]{}.

We now observe some basic properties of the $k$-leap concept:

-   If $A,B$ are in an odd-leap position, then necessarily each of $A,B$ is noncontractible and nonseparating.

-   It is not always true that $A,B$ in a $k$-leap position have geometric intersection number exactly $k$, but the parity of the two numbers is preserved. Particularly, $A,B$ are in an odd-leap position if and only if their geometric intersection number is odd. (We will not directly use this fact herein, though.)

-   We will later prove (Lemma \[lem:3pp\]) that the set of embedded cycles that are odd-leaping a given cycle $A$ satisfies the useful [*$3$-path condition*]{} (cf. [@MT01 Section 4.3]).

Stretch of an embedded graph
----------------------------

In the quest for another embedding density parameter suitable for capturing the two-dimensional character of the toroidal expanse and crossing number problems, we put forward the following concept improving upon the original “orthogonal width” of [@HS07].

\[def:stretch\] Let $G$ be a graph embedded in an orientable surface $\Sigma$. The [*stretch $\stretch(G)$ of $G$*]{} is the minimum value of $\len(A)\cdot\len(B)$ over all pairs of cycles $A,B\subseteq G$ that are in a one-leap position in $\Sigma$.

As we noted above, if $A,B$ are in an odd-leap position, then both $A$ and $B$ are noncontractible and nonseparating. Thus it follows that $\stretch(G)\geq\ewn(G)^2$. We postulate that stretch is a natural two-dimensional analogue of edge-width, a well-known and often used embedding density parameter. Actually, one may argue that the dual edge-width is a more suitable parameter to measure the density of an embedding, and so we shall mostly deal with [*dual stretch*]{}—the stretch of the topological dual $G^*$—later in this paper (starting since Lemma \[lem:cr-stretch-torus\] and Section \[sec:mainresults\]). Analogously to face-width, we can also define the [*face stretch*]{} of $G$ as one quarter of the stretch of the vertex-face incidence graph of $G$, and this is to be discussed later in Section \[sec:facestretch\].

We note in passing that although our paper does not use nor provide an algorithm to compute the stretch of an embedding, this can be done efficiently on any surface [@CCH13].

We now prove several basic facts about the stretch of an embedded graph. We start with an easy observation.

\[lem:thstr\] If $C$ is a nonseparating cycle in an embedded graph $G$, and $P$ is a $C$-switching ear in $G$, then $\stretch(G)\leq\len(C)\cdot\big(\len(P)+\frac12\len(C)\big)
    \leq2\len(C)\cdot\len(P)$.

The ends of $P$ partition $C$ into two paths $C_1,C_2\subseteq C$, which we label so that $||C_1|| \le ||C_2||$. (In a degenerate case, $C_1$ can be a single vertex). Thus $\len(C_1)\leq\frac12\len(C)$. Since $C$ and $P\cup C_1$ are in a one-leap position, we have $\stretch(G)\leq\len(C)\cdot(\len(P)+\len(C_1))\leq\len(C)\cdot2\len(P)$.

A tight relation of stretch to the topic of our paper is illustrated in the following claims.

\[lem:cr-stretch-torus\] If $G$ is a graph embedded in the torus, then $\crg(G)\leq\stretch(G^*)$.

Let $\alpha,\beta\subseteq G^*$ be a pair of dual cycles witnessing $\stretch(G^*)$, and let $K:=E(\alpha)^*$, $L:=E(\beta)^*\sem K$, and $M:=E(\alpha\cap \beta)^*$. Note that $K,L$, and $M$ are edge sets in $G$. Then, by cutting $G$ along $\alpha$, we obtain a plane (cylindrical) embedding $G_0$ of $G-K$. It is easily possible to draw the edges of $K$ into $G_0$ in one parallel “bunch” along the fragment of $\beta$ such that they cross only with edges of $L$ and $M\subseteq K$ (indeed, crossings between edges of $K$ are necessary when $M\not=\emptyset$), thus getting a drawing of $G$ in the plane. See Figure \[fig:addedges\]. The total number of crossings in this particular drawing, and thus the crossing number of $G$, is at most $|K|\cdot|L|+|K|\cdot|M|=
|K|\cdot(|L|+|M|)=\len(\alpha)\cdot\len(\beta)=\stretch(G^*)$.

\[cor:texp-stretch-torus\] If $G$ is a graph embedded in the torus, then $\Tex(G)\leq12\stretch(G^*)$.

This follows immediately using Corollary \[cor:crossing-texp\].

We finish this section by proving an analogue of Lemma \[lem:dew2\] for the stretch of an embedded graph, showing that this parameter cannot decrease too much if we cut the embedding through a short cycle. This will be important to us since cutting through handles of embedded graphs will be our main inductive tool in the proofs of lower bounds on $\crg(G)$ and $\Tex(G)$.

\[lem:str4\] Let $G$ be a graph embedded in the orientable surface $\Sigma_g$ of genus $g\geq2$, and let $C$ be a nonseparating cycle in $G$ of length $\len(C)=\ewn(G)$. Then $\stretch(G\cutt C)\geq\frac14\stretch(G)$.

Let $c_1,c_2$ be the two vertices of $G\cutt C$ that result from cutting through $C$, i.e., $\{c_1,c_2\}=V(G\cutt C)\sem V(G)$. Suppose that $\stretch(G\cutt C)=ab$ is attained by a pair of one-leaping cycles $A,B$ in $G\cutt C$, with $a=\len(A)$ and $b=\len(B)$. Our goal is to show that $\stretch(G)\leq4ab$. Using Lemma \[lem:dew2\] and the fact that both $A,B$ are nonseparating, we get $$\label{eq:abrho}
a,b\geq\ewn(G\cutt C)\geq\frac12\ewn(G)=\frac12\len(C)
.$$

Suppose first that both $c_1,c_2\in V(A\cup B)$. Then there exists a path $P\subseteq A\cup B$ connecting $c_1$ to $c_2$ such that $\len(P)\leq\frac12(a+b)$. Clearly, its lift $\hat P$ is a $C$-switching ear in $G$, and so by Lemma \[lem:thstr\] and (\[eq:abrho\]), $$\begin{aligned}
\stretch(G)\;&\leq\; \len(C)\cdot\big(\len(\hat P)+\frac12\len(C)\big)
 \leq\len(C)\cdot\frac12(a+b+\len(C))
\\
  &\leq\; \frac12(2ba+2ab+4ab)=4ab=4\,\stretch(G\cutt C)
.\end{aligned}$$

Finally suppose that, up to symmetry, $c_2\not\in V(A\cup B)$ but possibly $c_1\in V(A\cup B)$. Consider the lift $\hat A$ in $G$ (which is a $C$-ear in the case $c_1\in V(A)$). We define $\bar A$ to be $\hat A$ if $\hat A$ is a cycle, and otherwise $\bar A=\hat A\cup C_0$ where $C_0\subseteq C$ is a shortest subpath with the same ends in $C$ as $\hat A$. We define $\bar B$ analogously. With the help of a simple case-analysis, it is straightforward to verify that the cycles $\bar A,\bar B$ form a one-leaping pair in $G$, and so again using Lemma \[lem:thstr\] we obtain $$\begin{aligned}
\stretch(G)\;&\leq\; \len(\bar A)\cdot\len(\bar B)\leq (a+\frac12\len(C))\cdot(b+\frac12\len(C))
\\  &\leq\; (a+a)\cdot(b+b)=4ab=4\,\stretch(G\cutt C).\tag*{\qedhere}\end{aligned}$$

Breakdown of the proof of Theorem \[thm:main-overview\] {#sec:mainresults}
=======================================================

In this section we shall state the results leading to the proof of Theorem \[thm:main-overview\], which is given in Section \[sub:mainproof\]. The proofs of (most of) these statements are long and technical, and so they are deferred to the later sections of the paper.

To reach our main goal, i.e., to provide a proof for Theorem \[thm:main-overview\], we aim to:

-   extend the upper estimate of Lemma \[lem:cr-stretch-torus\] to surfaces of higher genus than the torus; and

-   provide asymptotically matching lower bounds on $\crg(G)$ and $\Tex(G)$ in terms of the dual stretch of $G$.

While the upper bounds are given (cf. Lemma \[lem:cr-stretch-torus\]) for the crossing number, the lower bounds here will be investigated for the toroidal expanse. At first glance, goal (I) would appear to be much easier than (II), but it is not really so straightforward due to some complications in expressing the upper bound (cf. Theorem \[thm:upper-cr\] below). Such difficulties are to be expected: for instance, a graph embedded in the double torus could have a huge toroidal grid living in one of the handles, and yet very small dual stretch due to a very small dual edge width in the other handle.

Since we will frequently deal with dual graphs in our arguments, we introduce several conventions in order to help comprehension. When we add an adjective [*dual*]{} to a graph term, we mean this term in the topological dual of the (currently considered) graph. We will denote the faces of an embedded graph $G$ using lowercase letters, treating them as vertices of its dual $G^*$. As we already mentioned in Section \[sub:gdes\], we use lowercase Greek letters to refer to subgraphs (cycles or paths) of $G^*$, and when there is no danger of confusion, we do not formally distinguish between a graph and its embedding. In particular, if $\alpha\subseteq G^*$ is a dual cycle, then $\alpha$ also refers to the loop on the surface determined by the embedding $G$. Finally, we will denote by $\ewnd(G):=\ewn(G^*)$ the nonseparating edge-width of the dual $G^*$ of $G$, and by $\stretchd(G):=\stretch(G^*)$ the dual stretch of $G$.

Estimating the toroidal expanse {#sub:toridalexp}
-------------------------------

We first give some basic lower bound estimates for the toroidal expanse, aimed at goal (II) above. These estimates ultimately rely on the following basic result, which appears to be of independent interest. Loosely speaking, it states that if a graph has two collections of cycles that mimic the topological properties of the cycles that build up a $p\times q$-toroidal grid, then the graph does contain such a grid as a minor. We say that a pair $(C,D)$ of curves in the torus is a [*basis*]{} (for the fundamental group) if there are no integers $m,n$ such that $C^m$ is homotopic to $D^n$.

\[thm:two-cycle-families\] Let $G$ be a graph embedded in the torus. Suppose that $G$ contains a collection $\{C_1,\dots,C_p\}$ of $p\geq3$ pairwise disjoint, pairwise homotopic cycles, and a collection $\{D_1,\dots,D_q\}$ of $q\geq3$ pairwise disjoint, pairwise homotopic cycles. Further suppose that the pair $(C_1,D_1)$ is a basis. Then $G$ contains a $p\times q$-toroidal grid as a minor.

The proof of this statement is in Section \[sec:grids\].

Now recall that in the torus $\ewn(G)=\ew(G)$, and so $\fw(G)\geq\frac{\ewnd(G)}{\lfloor\Delta(G)/2\rfloor}$. Hence, for instance, one can formulate Theorem \[thm:deGS\] in terms of nonseparating dual edge-width. Along these lines we shall derive the following as a consequence of Theorem \[thm:two-cycle-families\] (the proof is also in Section \[sec:grids\]):

\[thm:agrid-torus\] Let $G$ be a graph embedded in the torus and $k:=\ewnd(G)$. Let $\ell$ be the largest integer such that, in the dual graph $G^*$, there exists a dual cycle $\alpha$ of length $k$ and the shortest $\alpha$-switching dual ear has length $\ell$ (recall from Lemma \[lem:kl2\] that $\ell\geq k/2$). If $k\geq5\lfloor\Delta(G)/2\rfloor$, then $G$ contains as a minor the toroidal grid of size $$\left\lceil\frac \ell{\lfloor\Delta(G)/2\rfloor}\right\rceil
        \>\times\>
    \left\lfloor\frac23\left\lceil
        \frac k{\lfloor\Delta(G)/2\rfloor}
        \right\rceil\right\rfloor
\,.\smallskip$$

Hence the toroidal expanse of $G$ is at least $\big\lceil\frac \ell{\lfloor\Delta(G)/2\rfloor}\big\rceil
\cdot\big\lfloor\frac23\lceil\frac k{\lfloor\Delta(G)/2\rfloor}\rceil\big\rfloor$. On the other hand, since $\fw(G)\ge\frac
k{\lfloor\Delta(G)/2\rfloor}$, by Theorem \[thm:deGS\] it follows that the toroidal expanse of $G$ is at least $\big\lfloor\frac23\big\lceil\frac
k{\lfloor\Delta(G)/2\rfloor}\big\rceil\big\rfloor^2$. Therefore our estimate becomes useful roughly whenever $\ell>\frac23k$. Now by Lemma \[lem:thstr\] (applied to $G^*$), we have $\stretch^*(G) \le
k\cdot(\ell + k/2)$, and so $\ell>\frac23k$ whenever $\stretch^*(G)
> \frac{7}{6}k^2$.

Moreover, Theorem \[thm:agrid-torus\] can be reformulated in terms of $\stretch^*(G)$ (instead of “$\ell\cdot k$”). This reformulation is important for the general estimate on the toroidal expanse of $G$:

\[cor:agrid-torus\] Let $G$ be a graph embedded in the torus with $\ewnd(G)\geq5\lfloor\Delta(G)/2\rfloor$. Then $$\Tex(G)\>\geq\> \frac{2}{7}\,
    \big\lfloor{\Delta(G)}/2\big\rfloor^{-2} \cdot\stretchd(G)
    \>\geq\> \frac87\Delta(G)^{-2} \cdot\stretchd(G)
\,.$$ Furthermore, for any $\varepsilon>0$ there is a $k_0:=k_0(\Delta,\varepsilon)$ such that if $\ewnd(G)> k_0$, then $\Tex(G)\geq(\frac8{21}-\varepsilon)\cdot
    \lfloor{\Delta(G)}/2\rfloor^{-2}\cdot\stretchd(G)$.

For the proof of this statement, we again refer to Section \[sec:grids\].

Stepping up to orientable surfaces of genus $g>1$, we use Lemmas \[lem:dew2\] and \[lem:str4\] and Corollary \[cor:agrid-torus\] iteratively ($g-1$ times), cutting through shortest nonseparating dual cycles. This easily leads by induction to the following lower estimate:

\[cor:agrid-all\] Let $G$ be a graph embedded in the orientable surface $\Sigma_g$, $g\geq1$, such that $\ewnd(G)\geq5\cdot2^{g-1}\lfloor\Delta(G)/2\rfloor$. Then $$\Tex(G)\>\geq\> \frac{2}{7}\,4^{1-g}
    \big\lfloor{\Delta(G)}/2\big\rfloor^{-2} \cdot\stretchd(G)
    \>\geq\> \frac17\,2^{5-2g}\Delta(G)^{-2} \cdot\stretchd(G)
\,.\tag*{\qed}$$

This bound is, unfortunately, not strong enough to give the desired conclusion for $g\geq2$, but it is nevertheless useful in the course of deriving a stronger estimate later on (cf. Lemma \[lem:kl-to-stretch\]).

Algorithmic upper estimate for higher surfaces
----------------------------------------------

We now tackle task (I): to give an algorithmically efficient upper bound on the crossing number of a graph embedded in $\Sigma_g$.

Peter Brass conjectured the existence of a constant $c$ such that the crossing number of a toroidal graph on $n$ vertices is at most $c\Delta n$. This conjecture was proved by Pach and Tóth [@pachtoth]. Moreover, Pach and Tóth showed that for every orientable surface $\Sigma$ there is a constant $c_\Sigma$ such that the crossing number of an $n$-vertex graph embeddable on $\Sigma$ is at most $c_\Sigma \Delta n$; this result was extended to any surface by B[ö]{}r[ö]{}czky, Pach, and Tóth [@BPT06]. The constant $c_\Sigma$ proved in these papers is exponential in the genus of $\Sigma$. This was later refined by Djidjev and Vrt’o [@DV12], who decreased the bound to $\ca O(g\Delta n)$, and proved that this is tight within a constant factor.

At the heart of these results lies the technique of (perhaps recursively) cutting along a suitable [*planarizing*]{} subgraph (most naturally, a set of short cycles), and then redrawing the missing edges without introducing too many crossings. Our techniques and aims are of a similar spirit, although our cutting process is more delicate, due to our need to (eventually) find a matching lower bound for the number of crossings in the resulting drawing. Our cutting paradigm is formalized in the following definition.

\[def:good-planarizing\] Let $G$ be a graph embedded in the orientable surface $\Sigma_g$. A sequence $(G_1,C_1),(G_2,C_2), \dots, (G_g,C_g)$ is called a [*good planarizing sequence for $G$*]{} if the following holds for $i=1,\dots,g$, letting $G_0=G$:

-   $G_i$ is a graph embedded in $\Sigma_{g-i}$,

-   $C_i$ is a nonseparating cycle in $G_{i-1}$ of length $\ewn(G_{i-1})$, and

-   $G_i$ results by cutting the embedding $G_{i-1}$ through $C_i$.

We implicitly associate such a planarizing sequence with the values $\{k_i,\ell_i\}_{i=1,\ldots,g}$, where $k_i=\len(C_i)$ and $\ell_i$ is the length of a shortest $C_i$-switching ear in $G_{i-1}$, for $i=1,\dots,g$.

In order to upper bound the crossing number of an embedded graph, we make use of good planarizing sequences in the dual graph, as stated in the following result.

\[thm:upper-cr\] Let $G$ be a graph embedded in $\Sigma_g$. Let $(G_1^*,\gamma_1), \dots, (G_g^*,\gamma_g)$ be a good planarizing sequence for the topological dual $G^*$, with associated lengths $k_1,\ell_1,\dots,k_g,\ell_g$. Then $$\label{eq:uppercr}
\crg(G)\>\leq\>
    3\cdot\left(2^{g+1}-2-g\right)\cdot\max
         \{k_i\ell_i\}_{i=1,2,\ldots,g}
\,.$$ There is an algorithm that produces a drawing of $G$ in the plane with at most crossings in time $\ca O(n\log n)$ for fixed $g$.

The proof of this theorem is given in Section \[sec:drawing-upper\].

Bridging the approximation gap
------------------------------

Let us briefly revise where we stand in our way towards proving Theorem \[thm:main-overview\]. The right hand side of part (a) already follows from Corollary \[cor:crossing-texp\], and so to finish this part we need an estimate of the form $\Tex(G)=\Omega(\crg(G))$. We currently have a lower bound for $\Tex(G)$ in terms of $\stretch^*(G)$ (Corollary \[cor:agrid-all\]) and an upper bound for $\crg(G)$ in terms of $\max \{k_i\ell_i\}$. It may thus appear that our next task is to bridge the gap by proving that $\stretchd(G) = \Omega(\max
\{k_i\ell_i\})$. As it happens, no such statement is true in general, and so we need to find a way around this difficulty.

The following is a key technical claim that allows us to bridge the aforementioned gap.

\[lem:kl-to-stretch\] Let $H$ be a graph embedded in the orientable surface $\Sigma_g$. Let $k:=\ewnd(H)$, and let $\ell$ be the largest integer such that there is a cycle $\gamma$ of length $k$ in $H^*$ whose shortest $\gamma$-switching ear has length $\ell$. Assume $k\geq2^g$. Then there exists an integer $g'$, $0< g'\leq g$, and a subgraph $H'$ of $H$ embedded in $\Sigma_{g'}$ such that $$\ewnd(H')\geq 2^{g'-g}k
    \qquad\mbox{and}\qquad
\stretchd(H')\geq 2^{2g'-2g}\cdot k\ell
\,.$$

In a nutshell, the main idea behind the proof of this statement is to cut along handles that (may) cause small stretch, until we arrive to the desired toroidal $\Omega(k\times\ell)$ grid.

The arguments required to prove Lemma \[lem:kl-to-stretch\] span two sections. In Section \[sec:more\] we establish several basic results on the stretch of an embedded graph. As we believe this new parameter may be of independent interest, it makes sense to gather these results in a standalone section for possible further reference. The proof of Lemma \[lem:kl-to-stretch\] is then presented in Section \[sec:finding\].

The importance of Lemma \[lem:kl-to-stretch\] is its crucial role in establishing the following result, the final step in bridging the approximation gap.

\[cor:kl-to-stretch\] Let $G$ be a graph embedded in $\Sigma_g$. Let $(G_1^*,\gamma_1), \dots, (G_g^*,\gamma_g)$ be a good planarizing sequence of $G^*$, with associated lengths $k_1,\ell_1,\dots,k_g,\ell_g$. Suppose that $\ewnd(G)\geq5\cdot2^{g-1}\lfloor\Delta(G)/2\rfloor$. Then $$\Tex(G) \>\geq\> 
\frac{1}{7}\,2^{3-2g}
        \big\lfloor{\Delta(G)}/2\big\rfloor^{-2}
    \cdot \max \{k_i\ell_i\}_{i=1,2,\dots,g}
\,.$$ Consequently, $$\crg(G) \>\geq\> 
\frac{1}{21}\,2^{1-2g}
        \big\lfloor{\Delta(G)}/2\big\rfloor^{-2}
    \cdot \max \{k_i\ell_i\}_{i=1,2,\dots,g}
\,.$$

Let $j$ be the smallest integer such that $k_j\ell_j=\max \{k_i\ell_i\}_{
i=1,2,\dots,g}$, and let $H:=G_{j-1}$ (in case $j=1$, recall that we set $G_0:=G$). Thus $H$ is embedded in a surface of genus $g_1=g-j+1$. An iterative application of Lemma \[lem:dew2\] yields that $\ewnd(H)/\lfloor\Delta(H)/2\rfloor\geq
5\cdot2^{g-1}\cdot2^{g_1-g} =5\cdot2^{g_1-1}$.

We now apply Lemma \[lem:kl-to-stretch\] to $H$. Thus the resulting graph $H'$ of genus $g'\geq1$ satisfies $\ewnd(H')/\lfloor\Delta(H')/2\rfloor\geq5\cdot2^{g'-1}$ and $\stretchd(H')\geq 2^{2g'-2g_1}\cdot k_j\ell_j\geq 2^{2g'-2g}\cdot
k_j\ell_j$. Note that, even though $H^*=G^*_{j-1}$ may not be a subgraph of $G^*$, we have that $H$ (and thus $H'$) is a subgraph of $G$, and so $\Tex(G) \geq \Tex(H')$. Using Corollary \[cor:agrid-all\] we finally get $$\begin{aligned}
\Tex(G)\geq& \,\Tex(H') \>\geq\> \frac{2}{7}\,4^{1-g'}
    \big\lfloor{\Delta(H')}/2\big\rfloor^{-2} \cdot\stretchd(H')
\\
    \geq&\>  \frac{1}{7}\,2^{3-2g'}
    \big\lfloor{\Delta(G)}/2\big\rfloor^{-2}
        \cdot2^{2g'-2g}k_j\ell_j
    \>=\>\frac{1}{7}\,2^{3-2g}
    \big\lfloor{\Delta(G)}/2\big\rfloor^{-2} \cdot k_j\ell_j
\,.\end{aligned}$$ The second inequality then follows immediately by Corollary \[cor:crossing-texp\].

Proof of Theorem \[thm:main-overview\] {#sub:mainproof}
--------------------------------------

Having deferred the long and technical proofs of the previous subsections for the later sections of the paper, all the ingredients are now in place to prove Theorem \[thm:main-overview\].

The right hand side inequality in (a) follows from Corollary \[cor:crossing-texp\] (with $c_1=12$), and the left hand side follows at once by combining Theorem \[thm:upper-cr\] and Corollary \[cor:kl-to-stretch\]. Finally we note that part (b) follows from Theorem \[thm:upper-cr\] and (the crossing number inequality in) Corollary \[cor:kl-to-stretch\].

Finding grids in the torus {#sec:grids}
==========================

In this section we prove Theorems \[thm:two-cycle-families\] and \[thm:agrid-torus\] and Corollary \[cor:agrid-torus\].

Let $\alpha, \beta$ be oriented simple closed curves such that $(\alpha,\beta)$ is a basis, and such that $\alpha$ and $\beta$ intersect (cross) each other exactly once. Using a standard surface homeomorphism argument (cf. [@St93]), we may assume without loss of generality that each $C_i$ has the same homotopy type as $\alpha$ (we assign an orientation to the cycles $C_i$ to ensure this). Thus it follows that the cycles $D_j$ may be oriented in such a way that there exist integers $r\ge 0,s\ge 1$ such that the homotopy type of each $D_j$ is $\alpha^r\beta^s$.

We assume without loss of generality that $p\geq q\geq3$. We let $C_+:=C_1\cup C_2\cup\dots\cup
C_p$ and $D_+:=D_1\cup D_2\cup\dots\cup D_q$. We shall assume that among all possible choices of the collections $\{C_1,\dots,C_p\}$ and $\{D_1,\ldots,D_q\}$ that satisfy the conditions in the theorem (for the given values of $p$ and $q$), our collection $\cc:=\{C_1,\ldots,C_p\}$ minimizes $|E(C_+)\sem E(D_+)|$.

The indices of the $C_i$-cycles (respectively, the $D_j$-cycles) are read modulo $p$ (respectively, modulo $q$). We may assume that the cycles $C_1,C_2,\dots,C_p$ appear in this cyclic order around the torus; that is, for each $i=1,2,\ldots,p$, one of the cylinders bounded by $C_i$ and $C_{i+1}$ does not intersect any other curve in $\cc$. Moreover, we may choose this labeling so that $\beta$ intersects $C_1,C_2,\ldots,C_p$ in this cyclic order.

At first glance it may appear that it is easy to get the desired grid as a minor of $C_+\cup D_+$, since every $D_j$ has to intersect each $C_i$ in some vertex of $G$ (this follows since each pair $(C_i,D_j)$ is a basis). There are, however, two possible complications. First, two cycles $C_i, D_j$ could have many “zigzag” intersections, with $D_j$ intersecting $C_i$, then $C_{i+1}$, then $C_i$ again, etc. Second, $D_j$ may “wind” many times in the direction orthogonal to $C_i$. These are the problems to overcome in the upcoming proof.

We start by showing that, even though we may intersect some $C_i$ several times when traversing some $D_j$, it follows from the choice of $\cc$ that, after $D_j$ intersects $C_i$, it must hit either $C_{i-1}$ or $C_{i+1}$ before coming back to $C_i$.

\[clm\_ear\] No $C_+$-ear contained in $D_+$ has both ends on the same cycle $C_i$.

Suppose that there is a $C_+$-ear $P\subset D_+$ with both ends on the same $C_i$. Modify $C_i$ by following $P$ in the appropriate section, and let $C_i'$ be the resulting cycle. The families $\{C_1,\ldots,C_{i-1},C_i',C_{i+1},\ldots ,C_p\}$ and $\{D_1,\ldots,D_q\}$ satisfy the conditions in the theorem. The fact that $|E(C_1\cup \cdots \cup C_{i-1} \cup C_{i}' \cup C_{i+1} \cdots \cup C_p)
\setminus E(D_+)| < |E(C_+ \setminus D_+)|$ contradicts the choice of $\{C_1,\ldots,C_p\}$.

For any cycle $C$, a [*quasicycle*]{} is a graph-homomorphic image of $C$ without degree-$1$ vertices, implicitly retaining its cyclic ordering of vertices.

Let $D_j'$ be a quasicycle in $G$ homotopic to $D_1$, with its same orientation. We say that $D_j'$ is [*$C_+$-ear good*]{} if (cf. Claim \[clm\_ear\]) no $C_+$-ear contained in $D_j'$ has both ends on the same $C_i$. The [*rank*]{} $s_j$ of $D_j'$ is the number of connected components of $C_+\cap D_j'$. By traversing $D_j'$ once and registering each time it intersects a curve in $\cc$, starting with (some intersection with) $C_1$, we obtain an [*intersection sequence*]{} $a_j(i)$, $i=1,\dots,s_j$, where each $a_j(i)$ is in $\{1,\dots,p\}$. Since we chose the starting point of the traversal of $D_j'$ so that the first curve of $\cc$ it intersects is $C_1$, it follows that $a_j(1)=1$. We read the indices of this subsequence modulo $s_j$. We denote by $Q_{j,t}$, $t=1,2,\dots,s_j$, the path of $D_j'$ (possibly a single vertex) forming the corresponding intersection with the cycle $C_{a_j(t)}$, and by $T_{j,t}$ the path of $D_j'$ between $Q_{j,t}$ and $Q_{j,t+1}$. If $D_j'$ is $C_+$-ear good then $a_j(t+1)\not=a_j(t)$, and hence in this case $|a_j(t+1)-a_j(t)|\in\{1,p-1\}$ for $t=1,2,\dots,s_j$.

A collection of $C_+$-ear good quasicycles $D_1',D_2',\dots,D_q'$ in $G$ is [*quasigood*]{} if it satisfies the property that whenever $D_n'$ intersects $D_m'$ in a path $P$ (counting also the case of a self-intersection with $m=n$), the following hold up to symmetry between $n$ and $m$: (i) $P\subseteq Q_{n,x}$ for an appropriate index $x$ of the intersection sequence of $D_n'$ for which $a_n(x-1)=a_n(x+1)$ and $a_n(x)-a_n(x-1)\in\{1,1-p\}$; and (ii) the path $T_{n,x-1}\cup Q_{n,x}\cup T_{n,x}$ of $D_n'$ stays locally on one side of the (embedded) quasicycle $D_m'$. Informally, this means that if $D_n'$ intersects $D_m'$ in $P$, then $D_n'$ makes a $C_{a_n(x-1)}$-ear with $P$ “touching” $D_m'$ from the left side. For further reference we say that $D_n'$ is locally on the [*left side*]{} of the intersection $P$.

Since $D_j$ is clearly a $C_+$-ear good quasicycle for each $j=1,2,\ldots,q$, it follows that $D_1,D_2,\ldots,D_q$ is a quasigood collection. Now among all choices of a quasigood collection $D_1',D_2',\dots,D_q'$ in $G$, we select one minimizing the sum of the ranks of its quasicycles. For each $D_j'$, as above we let $s_j$ denote its rank.

\[clm\_quasi\] For all $1\leq j\leq q$ the intersection sequence of $D_j'$ satisfies $a_j(t-1)\not=a_j(t+1)$ for any $1<t\leq s_j$. Consequently, $D_1',D_2',\dots,D_q'$ is a collection of pairwise disjoint cycles in $G$.

The conclusion that $D_1',D_2',\ldots,D_q'$ is a collection of pairwise disjoint cycles directly follows from the first statement in the claim, since it is a quasigood collection. We hence focus on the first statement in the following.

The main idea in the proof is quite simple: if $a_j(t-1)=a_j(t+1)$, then we could modify $D_j'$ rerouting it through $C_{a_j(t-1)}$ instead of $T_{j,t-1}\cup Q_{j,t}\cup T_{j,t}$, thus decreasing $s_j$ (and hence the total sum of the ranks) by $2$, and consequently contradicting the choice of $\dd:=\{D_1',D_2',\ldots,D_q'\}$. We now formalize this idea.

Let $\cylin_i$ denote the cylinder bounded by $C_i$ and $C_{i+1}$. Note that if for some $j,t$ we have $a_j(t-1)=a_j(t+1)$ and $a_j(t)-a_j(t-1)\in\{-1,p-1\}$, then necessarily for some $t'$ we must have $a_j(t'-1)=a_j(t'+1)$ and $a_j(t')-a_j(t'-1)\in\{1,1-p\}$. So, seeking a contradiction, we may suppose that there exist $j,t$ such that $a_j(t-1)=a_j(t+1)=i$ and $a_j(t)=i+1$. Then the path $P=T_{j,t-1}\cup Q_{j,t}\cup T_{j,t}$ is drawn in $\cylin_i$ with both ends on $C_i$ and “touching” (i.e., not intersecting transversally) $C_{i+1}$. We denote by $R_0\subset\cylin_i$ the open region bounded by $P$ and $C_i$, and by $P'$ the section of the boundary of $R_0$ not belonging to $D_j'$.

Assuming that $R_0$ is minimal over all choices of $j$ for which $a_j(t-1)=a_j(t+1)$, we show that no $D_m'$, $m\in\{1,\dots,q\}$, intersects $R_0$. Indeed, if some $D_m'$ intersected $R_0$, then $D_m'$ could not enter $R_0$ across $P$ by the “stay on one side” property of a quasigood collection. Hence $D_m'$ should enter and leave $R_0$ across $P'\subseteq C_i$, but not touch $Q_{j,t}\subseteq C_{i+1}$, by the minimality of $R_0$. But then, $D_m'$ would make a $C_+$-ear with both ends on $C_i$, contradicting the assumption that $D_m'$ is $C_+$-ear good.

Now we form $D_j^o$ as the symmetric difference of $D_j'$ with the boundary of $R_0$ (so that $D_j^o$ follows $P'$). To argue that $D_1',\dots,D_j^o,\dots,D_q'$ is a quasigood collection again, it suffices to verify all possible new intersections of $D_j^o$ along $P'$. Suppose there is an $D_n'$ such that its intersection $Q_{n,x}$ with $C_i$ contains some internal vertex of $P'$. Since $D_n'$ is disjoint from (the open region) $R_0$, it will “stay on one side” of $D_j^o$. If $Q_{n,x}$ intersects $D_j'$, then $D_n'$ must be locally on the left side of this intersection, and so it is also on the left side of the intersection with $D_j^o$. If, on the other hand, $Q_{n,x}$ is disjoint from $D_j'$, then the adjacent paths $T_{n,x-1}$ and $T_{n,x}$ have to connect to $C_{i-1}$ by Claim \[clm\_ear\], and so we have $a_n(x)=i$ and $a_n(x-1)=a_n(x+1)=i-1$ as required by the definition for $D_n'$ on the left side. Let $\dd^o$ be the collection derived from $\dd$ by substituting $D_j'$ with $D_j^o$. In every case, $\dd^o$ is quasigood as well, but the sum of the ranks of its elements is strictly smaller (by $2$) than it is for $\dd$. This contradicts the choice of $\dd$.

\[clm\_wonce\] There is a collection of $q$ pairwise disjoint, pairwise homotopic noncontractible cycles in $G$, each of which has a connected nonempty intersection with each cycle in $\cc$.

It follows from Claim \[clm\_quasi\] that the intersection sequence of each $D_j'$ is a $t$-fold repetition of the subsequence $\langle 1,2,\ldots,p\rangle$, for some nonnegative integer $t$. If $t=1$, we are obviously done, so assume $t \ge 2$. Our task is to “shortcut” each $D_j'$ such that it “winds only once” in the direction orthogonal to $\alpha$ (more formally, to modify each $D_j'$ so that its homotopy type is $\alpha^r \beta$ for some integer $r$).

Note that, for all $i=1,\dots,p$, every $C_i$-ear contained in any $D_j'$ is $C_i$-switching by Claim \[clm\_quasi\]. Each such ear naturally inherits an orientation from $D_j'$, so that after leaving $C_i$ it intersects $C_{i+1},
C_{i+2}, \ldots, C_{i-1}$ in this order, and then intersects $C_i$ again. Let $T_1 \subset D_1'$ be any $C_1$-ear, and let $x_1,y_1$ be their start and end points, respectively. Then let $W_1\subset C_1$ be (any) one of the two paths contained in $C_1$ with endpoints $x_1, y_1$. It is clear that the cycle $D_1''=T_1\cup W_1$ is a simple closed curve that has a connected nonempty intersection with each $C_i$. Our final task is to find, for each $j=2,\ldots,q$, a homotopic, similarly constructed cycle $D_j''$, so that the cycles $D_1'', D_2'',\ldots,D_j''$ are pairwise disjoint.

Since $D_1''$ is not homotopic to $D_1'$, every $D_j'$ has to intersect $D_1''$ in $W_1$; this intersection is a path $P_j$ (possibly a single vertex). Since the curves $D_j'$ are pairwise disjoint, it follows that the paths $P_j$ are also pairwise disjoint. For $j=2,\ldots,q$, let $x_j$ be the point in $P_j$ closest to $x_1$, and let $T_j'$ be the unique $C_1$-ear starting at $x_j$. Now let $T_j$ be the unique $C_j$-ear starting on a vertex in $T_j'$, and let $W_j\subset C_j$ be the path joining the ends of $T_j$ that is disjoint from $T_1$. Finally, set $D_j''=T_j\cup
W_j$, for $j=2,\ldots,q$. It is straightforward to check that the curves $D_1'', D_2'', \ldots, D_q''$ satisfy the required properties.

To conclude the proof of Theorem \[thm:two-cycle-families\], we let $\{D_1'', D_2'', \ldots, D_q''\}$ be the collection guaranteed by this last claim. For each $i=1,2,\ldots,p$ and $j=1,2,\ldots,q$, we contract the path $C_i\cap D_j''$ to a single vertex (unless it already is a single vertex). Since the curves $D_1'',D_2'',\ldots,D_q''$ are pairwise disjoint and pairwise homotopic, it directly follows that the resulting graph is isomorphic to a subdivision of the $p\times q$-toroidal grid.

First we show the following.

\[cl:ellcycles\] $G$ has a set of at least $\frac \ell{\lfloor\Delta/2\rfloor}$ pairwise disjoint cycles, all homotopic to $\alpha$.

Let $F$ be the set of those edges of $G$ intersected by $\alpha$. Let $\alpha_1, \alpha_2$ be loops very close to and homotopic to $\alpha$, one to each side of $\alpha$, so that the cylinder bounded by $\alpha_1$ and $\alpha_2$ that contains $\alpha$ intersects $G$ only in the edges of $F$. Now we cut the torus by removing the (open) cylinder bounded by $\alpha_1$ and $\alpha_2$, thus leaving an embedded graph $H:=G-F$ on a cylinder $\cylin$ with boundary curves (“rims”) $\alpha_1$ and $\alpha_2$. Let $\delta$ be a curve on $\cylin$ connecting a point of $\alpha_1$ to a point of $\alpha_2$, such that $\delta$ has the fewest possible points in common with the embedding $H$. We note that we may clearly assume that the $p$ points in which $\delta$ intersects $H$ are vertices.

We claim that $p\geq \frac \ell{\lfloor\Delta/2\rfloor}$. Indeed, if $p< \frac \ell{\lfloor\Delta/2\rfloor}$, then the union of all faces incident with the $p$ vertices intersected by $\delta$ would contain a dual path $\beta$ of length at most $p\cdot \lfloor\Delta/2\rfloor <
\frac \ell{\lfloor\Delta/2\rfloor}\cdot
\lfloor\Delta/2\rfloor=\ell$. Such $\beta$ would be an $\alpha$-switching dual ear in $G^*$ of length less than $\ell$, a contradiction.

We now cut open the cylinder $\cylin$ along $\delta$, duplicating each vertex intersected by $\delta$. As a result we obtain a graph $H'$ embedded in the rectangle with sides $\alpha_1,\delta_1,\alpha_2,\delta_2$ in this cyclic order, so that $\delta_1$ (respectively, $\delta_2$) contains $p$ vertices $w_i^1, i=1,2,\ldots,p$ (respectively, $w_i^2, i=1,2,\ldots,p$).

We note that there is no vertex cut of size at most $p-1$ in $H'$ separating $\{w_1^1,\dots,w_p^1\}$ from $\{w_1^2,\ldots,w_p^2\}$, for such a vertex cut would imply the existence of a curve $\varepsilon$ from $\alpha_1$ to $\alpha_2$ on $\cylin$ intersecting $H$ in fewer than $p$ points, contradicting our choice of $\delta$. Thus applying Menger’s Theorem we obtain $p$ pairwise disjoint paths from $\{w_1^1,\dots,w_p^1\}$ to $\{w_1^2,\ldots,w_p^2\}$ in $H'$. Moreover, it follows by planarity of $H'$ that each of these paths connects $w_i^1$ to the corresponding $w_i^2$ for $i=1,\dots,p$. By identifying back $w_i^1$ and $w_i^2$ for $i=1,\dots,p$, we get a collection of $p$ pairwise disjoint cycles in $H$, each of them homotopic to $\alpha$.

We have thus proved the existence of a collection $\cc$ of $\ell/\dee$ pairwise disjoint, pairwise homotopic noncontractible cycles. By Theorem \[thm:deGS\], since $\fw(G) \ge \ewnd(G)/\dee$, it follows that $G$ also contains two collections $\dd,\ee$ of cycles such that: (i) the cycles in $\dd$ are noncontractible, pairwise disjoint, and pairwise homotopic; (ii) the cycles in $\ee$ are noncontractible, pairwise disjoint, and pairwise homotopic; (iii) for any $D\in\dd$ and $E\in\ee$, the pair $(D,E)$ is a basis; and (iv) each of $|\dd|$ and $|\ee|$ is at least $\big\lfloor\frac23\lceil\frac k{\lfloor\Delta(G)/2\rfloor}\rceil\big\rfloor$. Let $C\in\cc$, $D\in\dd$, and $E\in\ee$. From properties (i)–(iii) it follows that either $(C,D)$ or $(C,E)$ is a basis. Therefore the result follows from Theorem \[thm:two-cycle-families\].

Let $k:=\ewnd(G)$, and let $\ell$ and $\alpha$ be as in Theorem \[thm:agrid-torus\]. By Lemma \[lem:thstr\], . Let $r=\big\lceil\frac k{\lfloor\Delta(G)/2\rfloor}\big\rceil$. Since $r\geq5$, it follows that $\lfloor2r/3\rfloor\geq\frac67(2r/3)=\frac47r$ (with equality at $r=7$). Letting $s=\big\lceil\frac\ell{\lfloor\Delta(G)/2\rfloor}\big\rceil$ we then get, by Theorem \[thm:agrid-torus\], $$\Tex(G) \geq s\cdot\left\lfloor\frac23r\right\rfloor\geq 
    \frac47rs \geq \frac47k\ell \cdot\big\lfloor{\Delta(G)}/2\big\rfloor^{-2}
    \geq \frac27\stretchd(G) \cdot\big\lfloor{\Delta(G)}/2\big\rfloor^{-2}
\,.$$ In order to get the better asymptotic estimate $\Tex(G)\geq(\frac8{21}-\varepsilon)\cdot
        \lfloor{\Delta(G)}/2\rfloor^{-2}\cdot\stretchd(G)$, we directly apply Theorem \[thm:deGS\] in the case $s\leq2r/3$; otherwise, we use the stronger bound $\stretchd(G)\leq
    k\ell+k\cdot k/2\leq k(\ell+3\ell/4)=\frac74k\ell$.

Drawing embedded graphs into the plane {#sec:drawing-upper}
======================================

In this section, we prove Theorem \[thm:upper-cr\]. That is, we provide an efficient algorithm that, given a graph $G$ embedded in some orientable surface, yields a drawing of $G$ (with a controlled number of crossings) in the plane. Although our algorithm takes an embedded graph as its input, we might as well take the non-embedded graph as input without any loss of efficiency; indeed, Mohar [@Mo99] showed that, for any fixed genus $g$, there is a linear time algorithm that takes as input any graph $G$ embeddable in $\Sigma_g$ and outputs an embedding of $G$ in $\Sigma_g$.

We start with an informal outline of the proof.

We proceed in $g$ steps, working at the $i$-th step with the pair $(G_i^*,\gamma_i)$. For convenience, let $G_0=G$, and define $F_i=E(G_{i-1})\sem E(G_{i})=E(\gamma_i)$. The idea at the $i$-th step is to cut from $G_{i-1}$ the edges intersected by $\gamma_i$ (that is, the set $F_i$). We could then to draw these edges into the embedded graph $G_i$ along the route determined by a $\gamma_i$-switching ear of length $\ell_i$ in $G_{i-1}$. This would result in at most $k_i(\ell_i+k_i)$ new crossings in $G_i$ (similarly as in Figure \[fig:addedges\]). For technical reasons, we consider routing the edges of each $F_i$ in one bunch (i.e., along the same route), even though routing every edge separately could perhaps save a small number of crossings.

In reality, the situation is not as simple as in the previous sketch. The main complication comes from the fact that subsequent cutting (step $j>i$) could “destroy” the chosen route for $F_i$ (or at least part of it). Then it would be necessary to perform a further re-routing for the edges of $F_i$ in step $j$. This could essentially happen in each subsequent step until the end of the process (when obtaining planar $G_g$).

We handle this complication in two ways: Proof-wise, we track a possible insertion route (and its necessary modifications) for $F_i$ through the full cutting process. In particular, we show that the final insertion route is never longer than $\ell_i+\ell_{i+1}+\dots+\ell_g$, for each index $i$. Another detail one has to take care of, is to ensure that such a detour for $F_i$ would not produce significantly more additional crossings than $k_j\ell_j$, over all $j=i+1,\ldots g$; this holds as long as $k_j$ is never much smaller than $k_i$ (cf. Lemma \[lem:dew2\]).

Algorithmically, we will reinsert all edges $\bigcup_{i=1}^g F_i$ only at the very end, into $G_g$. The previously tracked routes are then upper bounds for the so-achieved solution.

In the proof, we briefly use the concept of an *angle* of a pair of edges in an embedded graph. For this, we recall that the [ *rotation*]{} of a vertex $v$ in an embedded graph is the (say, counterclockwise, by convention) cyclic order in which the edges incident with $v$ leave this vertex. Suppose now that the rotation of a degree-$d$ vertex is $e_0,e_1,\ldots, e_{d-1}$, and let $(e_i,e_j)$ be an ordered pair. Then the [*angle*]{} of $(e_i,e_j)$ is the set of edges $\{e_i,
e_{i+1}, \ldots, e_{j-1}, e_j\}$ (with indices read modulo $d$).

As outlined in the sketch above, we proceed in $g$ steps. At the $i$-th step, for $i=1,2,\ldots,g$, we take the embedded graph $G_{i-1}$ and cut the surface open along $\gamma_i$, thus severing the edges in the set $F_i:=E(G_{i-1})\setminus E(G_i)=E(\gamma_i)$. This decreases the genus by one, and creates two holes, which we repair by pasting a closed disc on each hole. Thus we get the graph $G_i$ embedded in a compact surface with no holes.

\[cl:sumell\] Let $i=1,\ldots,g$, and let $f$ be an edge in $F_i$. Then, $f$ can be drawn into the plane graph $G_g$ with at most $\sum_{j=i}^g\ell_j$ crossings.

Let $i\in\{1,\ldots,g\}$ be fixed. In the graph $G_i$, we let $a,b$ denote the two new faces created by cutting $G_{i-1}$ along $\gamma_i$ (thus each of these faces contains one of the pasted closed discs). Let $f$ be an edge in $F_i$, with endpoints $f_a$ (incident with $a$ in $G_i$) and $f_b$ (incident with $b$ in $G_i$).

For each $j=i,i+1,\ldots,g$, we associate two faces $a_j(f), b_j(f)$ of $G_j$ with $f$. Loosely speaking, these faces are the natural heirs in $G_j$ of the faces $a$ and $b$, if we stand in $G_j$ on the vertices $f_a$ and $f_b$ (we note that $a,b$ are faces in $G_i$, but by the further cutting process, they may not be faces in $G_j$ for some $j > i$). The faces $a_j(f), b_j(f)$ are recursively defined as follows. First, let $a_i(f) = a$ and $b_i(f) = b$. Now suppose $a_{j-1}(f), b_{j-1}(f)$ have been defined for some $j$, $i< j \le g$. We then let $a_j(f)$ be the unique face $h$ of $G_j$ that satisfies the following: if $(e,e')$ is the pair of edges of $h$ incident with $f_a$, ordered so that the angle of $(e,e')$ in $G_{j}$ consists only of $e$ and $e'$, then the angle of $(e,e')$ in $G_{j-1}$ includes the edges of the face $a_{j-1}(f)$ that are incident with $f_a$. The face $b_j(f)$ is defined analogously.

The vertex $f_a$ (respectively, $f_b$) is incident to the face $a_g(f)$ (respectively, $b_g(f)$) in the plane embedding $G_g$. To finish the proof, it suffices to show that the dual distance between $a_g(f)$ and $b_g(f)$ in $G_g$ is at most $\sum_{j=i}^g\ell_j$. We prove this via induction over $j=i,i+1,\dots,g$, i.e., we show that the dual distance between $a_j(f)$ and $b_j(f)$ in $G_j$ is at most $\ell_i+\ell_{i+1}+\dots+\ell_j$.

This holds (with equality) for $j=i$ by the definition of $\ell_i$. For $j>i$, take a shortest dual path $\pi$ in $G_{j-1}$ connecting $a_{j-1}(f)$ to $b_{j-1}(f)$. Unless $\pi$ intersects $\gamma_j$, its length also bounds the dual distance in $G_j$. Assuming $\pi\cap\gamma_j\not=\emptyset$ in $G_{j-1}$, we can replace (in $G_j$) the section of $\pi$ between the first and the last intersection with $\gamma_j$ by a $\gamma_j$-switching ear of length $\ell_j$. It follows that the dual distance between $a_j(f)$ and $b_j(f)$ is at most $
\len(\pi)+\ell_j\leq \ell_i+\dots+\ell_{j-1}+\ell_j$, as claimed.

Now recall that $|F_i|=k_i$, for $i=1,\ldots,g$. From Claim \[cl:sumell\] it follows that the edges in $F_i$ can be added to the plane embedding $G_g$ by introducing at most $k_i \cdot \sum_{j=i}^g\ell_j$ crossings with the edges of $G_g$. This measure disregards any additionally crossings arising between edges of $F_i$. We add to $G_g$ the edges of $F_{g}$, then the edges of $F_{g-1}$, and so on. As we add the edges of $F_i$, in the worst case scenario each edge we add crosses every edge already or currently inserted; thus the total cost of adding the edges of $F_i$ is at most $k_i \cdot \sum_{j=i}^g\ell_j + k_i \cdot \sum_{j=i}^g k_j$. Overall, the edges $F_1 \cup F_2 \cup \cdots \cup F_g$ can be added to the plane embedding by introducing at most $\sum_{i=1}^g \left(k_i\cdot\sum_{j=i}^g (k_j+\ell_j)\right)$ crossings. Using that $2\ell_i\geq k_i$ (cf. Lemma \[lem:kl2\]), this process yields a drawing of $G$ in the plane with at most $$\begin{aligned}
\sum_{i=1}^g \left(k_i\cdot\sum_{j=i}^g (k_j+\ell_j)\right)\;&\leq\;
  \sum_{i=1}^g \left(k_i\cdot\sum_{j=i}^g 3\ell_j\right)
\\
  &=\; 3\sum_{j=1}^g \left(\ell_j\cdot\sum_{i=1}^j k_i\right)\end{aligned}$$ crossings. The inductive application of Lemma \[lem:dew2\] yields $k_i\leq2^{j-i}k_j$ for all $1\leq i<j\leq g$. Therefore $$\begin{aligned}
\nonumber
3\sum_{j=1}^g \left(\ell_j\cdot\sum_{i=1}^j k_i\right)\;&\leq\;
 3\sum_{j=1}^g \ell_jk_j(2^{j-1}+\dots+2^1+2^0)
\\\nonumber
  &=\;  3\sum_{j=1}^g k_j\ell_j(2^{j}-1)
\\\nonumber
  &\leq\; 3\max_{1\le i \le g} \{k_i\ell_i\}\cdot(2^1+2^2+\dots+2^g-g)
\\\label{eq:3M}
  &=\; 3\cdot(2^{g+1}-2-g)\cdot \max_{1\le i \le g} \{k_i\ell_i\}.\end{aligned}$$

We have thus shown how to produce a drawing of $G$ with at most $3\cdot(2^{g+1}-2-g)\cdot \max_{1\le i \le g} \{k_i\ell_i\}$ crossings. It remains to show how such a drawing can be computed efficiently from an embedding of $G$ in $\Sigma_g$. The algorithm runs two phases:

1.  A good planarizing sequence $(G_1^*,\gamma_1), \dots, (G_g^*,\gamma_g)$ for $G^*$ is computed using $g$ calls to the $\ca O(n\log n)$ algorithm of Kutz [@Ku06], which finds a cycle witnessing nonseparating edge-width in orientable surfaces. During the computation, we represent $G^*$ by its rotation scheme which allows fast implementation of the cutting operation as well.

2.  In the planar graph $G_g$, optimal insertion routes are found for all the missing edges $F=E(G)\sem E(G_g)$ using linear-time breadth-first search in $G_g^*$. A key observation is that we are looking for these insertion routes only between predefined pairs of faces $a_g(f)$ and $b_g(f)$ for each $f\in F$. Since each of $\{a_g(f) \ : f\in F_i\ \}$ and $\{b_g(f) \ : f\in F_i\ \}$ has at most $2^{g-i}$ elements for each $i=1,2,\ldots,g$, it follows that we need to perform at most $2^{g-1}+\dots+2^1+2^0<2^g$ searches in total (independently of $|F|$), a process that takes an overall linear time for fixed $g$. From the practical point of view, it may be worthwhile to mention that $|G_g|$ also serves as a natural upper bound for the considered faces.

In view of this, the overall runtime of the algorithm is $\ca O(n\log
n)$ for each fixed $g$.

More properties of stretch {#sec:more}
==========================

In this section, we establish several basic properties on the stretch of an embedded graph. Even though we could have alternatively included these in the next section, as we only require them in the proof of Lemma \[lem:kl-to-stretch\], we prefer to present them in a separate section, for an easier further reference of the basic properties of this new parameter which may be of independent interest.

We recall that a graph property $\ca P$ satisfies the [*$3$-path condition*]{} (cf. [@MT01 Section 4.3]) if the following holds: Let $T$ be a [*theta graph*]{} (a union of three internally disjoint paths with common endpoints) such that two of the three cycles of $T$ do not possess $\ca P$; then neither does the third cycle. In the proof of the following lemma we make use of halfedges. A [*halfedge*]{} is a pair $\langle e,v\rangle$ (“$e$ at $v$”), where $e$ is an edge and $v$ is one of the two ends of $e$.

\[lem:3pp\] Let $G$ be embedded on an orientable surface, and let $C$ be a cycle of $G$. The set of cycles of $G$ satisfies the $3$-path condition for the property of odd-leaping $C$. Furthermore, not all three cycles in any theta subgraph of $G$ can be odd-leaping $C$.

Let a theta graph $T\subseteq G$ be formed by three paths $T=T_1\cup T_2\cup T_3$ connecting the vertices $s,t$ in $G$. We consider a connected component $M$ of $C\cap T$. If $M=\emptyset$ or $M=C$, then the $3$-path condition trivially holds. Otherwise, $M$ is a path with ends $m_1,m_2$ in $G$. We denote by $f_1,f_2$ the edges in $E(C)\sem E(M)$ incident with $m_1,m_2$, respectively, and by $M^+$ the union of $M$ and the halfedges $\langle f_1,m_1\rangle$ and $\langle f_2,m_2\rangle$. We show that the number $q$ of leaps of $M^+$ summed over all three cycles in $T$ is always even.

If $m_i\not\in\{s,t\}$ for $i\in\{1,2\}$, then contracting the edge of $M$ incident to $m_i$ clearly does not change the number $q$. Iteratively applying this argument, we can assume that finally either (i) $m_1=m_2$ (and possibly $m_1\in\{s,t\}$), or (ii) $m_1=s$, $m_2=t$, and $M=T_1$. In case (i), $M^+$ leaps either none or two of the cycles of $T$ in the single vertex $m_1$, and so $q\in\{0,2\}$. Thus we assume for the rest of the proof that (ii) holds.

For $i=1,2,3$, let $e_i$ (respectively, $e_i'$) be the edge of $T_i$ incident with $s$ (respectively, $t$). By relabeling $e_1, e_2, e_3$ if needed, we may assume that the rotation around $s$ is one of the cyclic permutations $(e_1,f_1,e_2,e_3)$ or $(e_1,e_2,f_1,e_3)$. The rotation around $t$ could be any of the six cyclic permutations of $e_1',e_2',e_3',f_2$. This yields a total of twelve possibilities to explore. A routine analysis shows that in every case we get $q\in\{0,2\}$, except for the case in which the rotation around $s$ is $(e_1,e_2,f_1,e_3)$ and the rotation around $t$ is $(e_1',e_2',f_2,e_3')$; in this case, $M^+$ leaps twice the cycle $T_2\cup T_3$, and $q=4$.

Altogether, the number of leaps of $C$ summed over all three cycles in $T$ is even. Hence the number of cycles of $T$ which are odd-leaping with $C$ is also even, and the $3$-path condition follows.

The next claim shows that stretch (Definition \[def:stretch\]) could have been equivalently defined as an [*odd-stretch*]{}, using pairs of odd-leaping cycles instead of one-leaping cycles.

\[lem:odd-stretch\] Let $G$ be a graph embedded in an orientable surface. If $C,D$ is an odd-leaping pair of cycles in $G$, then $\stretch(G)\leq\len(C)\cdot\len(D)$.

We choose an odd-leaping pair $C,D$ that minimizes $\len(C)\cdot\len(D)$. Up to symmetry, $\len(C)\leq\len(D)$. Since $C\cap D\not=\emptyset$, there is a set $\ca D=\{D_1,\dots,D_k\}$ of pairwise edge-disjoint $C$-ears in $D$, such that $E(D_1)\cup\dots\cup E(D_k)=E(D)\sem E(C)$. By a simple parity argument, there exists a $C$-switching ear in $\ca D$. Hence if $|\ca D|=1$, then $C,D$ are one-leaping, and the lemma immediately follows.

If more than one $C$-ear in $\ca D$ is switching, then we pick, say, $D_1$ as the shorter of these. By the choice of $D$ we have $\len(D_1)\leq\frac12\len(D)$, and so by Lemma \[lem:thstr\] we have $$\stretch(G)\leq\len(C)\cdot\left(\len(D_1)+\frac12\len(C)\right)
 \leq\len(C)\cdot\left(\frac12\len(D)+\frac12\len(D)\right) =
 \len(C)\cdot\len(D)
\,,$$ as required.

In the remaining case, we have that $|\ca D|>1$ and exactly one $C$-ear in $\ca D$ (say $D_1$) is switching. We pick any $D_j\in\ca D$, $j>1$, let $u,v$ be the ends of $D_j$ on $C$, and compare the distance $d$ between $u$ and $v$ on $C$ with $\len(D_j)$. If $d>\len(D_j)$, then both cycles of $C\cup D_j$ containing $D_j$ are shorter than $\len(C)$, and one of them is odd-leaping with $D$ by Lemma \[lem:3pp\]. This contradicts the choice of $C$ (for the pair $C,D$, that is). Hence $\len(D_j)\geq d$, and summing these inequalities over all $j=1,\dots,k$ we get $\len(D_1)\leq\len(D)-s$, where $s$ is the distance between the ends of $D_1$ on $C$. Similarly as in Lemma \[lem:thstr\], we then get $$\stretch(G)\leq\len(C)\cdot(\len(D_1)+s)
 \leq\len(C)\cdot\left(\len(D)-s+s\right)
= \len(C)\cdot\len(D).\tag*{\qedhere}$$

\[lem:cutdew\] Let $H$ be a graph embedded in an orientable surface of genus $g\geq2$, and let $A,B\subseteq H$ be a one-leaping pair of cycles witnessing the stretch of $H$, such that $\len(A)\leq\len(B)$. Then $\ewn(H\cutt A)\geq\frac12\ewn(H)$.

Let $C$ be a nonseparating cycle in $H\cutt A$ of length $\ewn(H\cutt A)$. If its lift $\hat C$ is a cycle again, then (since $\hat C$ is nonseparating in $H$) $\ewn(H)\leq\len(\hat C)=\ewn(H\cutt A)$, and we are done. Thus we may assume that $\hat C$ contains an $A$-ear $P\subseteq\hat C$ such that $A\cup P$ is a theta graph. Let $A_1,A_2\subseteq A$ be the subpaths into which the ends of $P$ divide $A$. By Lemma \[lem:3pp\], exactly two of the three cycles of $A\cup P$ are odd-leaping with $B$. One of these cycles is $A$; let the other one, without loss of generality, be $A_1\cup P$. Then $\len(A_1\cup P)\geq\len(A)$ using Lemma \[lem:odd-stretch\], and so $\len(P)\geq\len(A_2)$. Furthermore, $A_2\cup P$ is nonseparating in $H$, and we conclude that $$\ewn(H)\leq\len(A_2\cup P)\leq
 2\len(P)\leq2\len(\hat C)=2\ewn(H\cutt A)
\,.\tag*{\qedhere}$$

At this point, an attentive reader may wonder why we do not use the cutting paradigm as in Lemma \[lem:cutdew\] in a good planarizing sequence for Theorem \[thm:upper-cr\] (Section \[sec:drawing-upper\]). Indeed, it would seem that the same proof as in Section \[sec:drawing-upper\] works in this new setting, and the added benefit would be an immediately matching lower bound in the form provided by Corollary \[cor:agrid-all\]. The caveat is that the proof of Theorem \[thm:upper-cr\] strongly uses the fact that subsequent cuts in a planarizing sequence do not involve [*much fewer*]{} edges (recall “$k_i\leq2^{j-i}k_j$ for all $1\leq i<j\leq g$” from the proof). If one cuts along the shortest cycle of a pair that witnesses the dual stretch, then the number of cut edges may jump up or down arbitrarily. Thus an attempted proof along the lines of the proof we gave in Section \[sec:drawing-upper\] would (inevitably?) fail at this point.

Finding a subgraph of large stretch {#sec:finding}
===================================

In this section we prove Lemma \[lem:kl-to-stretch\]. Therefore, we need to generalize the concepts of switching and leaping. Given an embedded graph $H$ and an embedded subgraph $D\subset G$, we want to talk about $D$-switching ears, and walks that are $k$-leaping $D$, also in cases when $D$ is a not necessarily a cycle. The essential property of a cycle used in these definitions is that it has two clearly defined sides. We generalize this feature (to subgraphs that are not necessarily cycles) to a property we call *polarity*.

Polarity
--------

Let $H$ be a graph cellularly embedded in a surface $\Sigma$, and let $D$ be a (not necessarily connected) subgraph of $H$. The [*$H$-induced*]{} embedding $\tilde D$ of the graph $D$ is determined by the system of $H$-rotations around vertices of $D$ restricted to $E(D)$. Intuitively, $\tilde D$ is obtained from the usual subembedding of $D$ in $\Sigma$ via replacing all non-cellular faces with discs. Notice that $\tilde D$ has a separate surface for each connected component of $D$. If $\tilde D$ can be face-bicolored, then we say that $D$ is [*bipolar in $H$*]{}, and we associate one chosen facial bicoloring of $\tilde D$ with $D$ (notice that this bicoloring is not unique when $D$ is not connected). We will refer to the facial colors of $\tilde D$ (white and black) as the [*$D$-polarities*]{} in $H$ (positive and negative, respectively).

More formally, for $v\in V(D)$ and $e\not\in E(D)$, the halfedge $\langle e,v\rangle$ has a [*positive*]{} ([*negative*]{}) $D$-polarity if the position of $e$ in the $H$-rotation around $v$ is between consecutive edges of a white (black) $\tilde D$-face. Clearly, a cycle in any orientable embedding is always bipolar. Also, if $D$ is bipolar, then it is Eulerian.

A $D$-ear $P$ is [*$D$-polarity switching*]{} if the halfedges of $P$ incident with the ends of $P$ are of distinct $D$-polarities. If $D$ is a cycle, then being “$D$-polarity switching” is equivalent to being “$D$-switching”. We now consider a (possibly closed) walk $W\subseteq H$. A proper subwalk $M$ of $W$ is called a [*polarity leap (of $W$ and $D$)*]{} if

-   $M\subseteq D\cap W$ and neither the edge $f_0$ preceding $M$ in $W$ nor the edge $f_1$ succeeding $M$ in $W$ belong to $D$ (in particular, $M$ is neither a prefix nor a suffix of $W$), and

-   the halfedges of $f_0,f_1$ incident with $M$ are of distinct $D$-polarities.

We say that $W$ is [*odd-leaping*]{} bipolar $D$ if the number of all proper subwalks of $W$ which are polarity leaps is odd; otherwise $W$ is [*even-leaping*]{} $D$. Notice that being “one-leaping” (Definition \[def:leaping\]) implies “odd-leaping” in this new sense.

The workhorse
-------------

Informally speaking, the intuition behind our proof of Lemma \[lem:kl-to-stretch\] is to suitably cut down the embedding $G$ to a smaller surface (destroying handles causing small stretch; remember our aim is to find a subgraph with large stretch), while approximately preserving $\gamma$ and its switching distance.

The main tool behind the proof of Lemma \[lem:kl-to-stretch\] is the following lemma. To make sense of this statement, and to grasp how this easily leads to the proof of Lemma \[lem:kl-to-stretch\], we refer the reader to the informal discussion provided immediately after the statement.

\[lem:cutstep\] Let $H$ be a graph embedded in an orientable surface. Suppose that:

-   there is a bipolar dual subgraph $\delta$ in $H^*$;

-   there exists a closed walk in $H^*$ that is odd-leaping $\delta$; and

-   the shortest $\delta$-polarity switching ear in $H^*$ has length $h$.

Let $\alpha,\beta$ be a one-leaping pair (any one) of dual cycles in $H^*$ such that $\len(\alpha)\leq\len(\beta)$ and $\stretchd(H)=\len(\alpha)\cdot\len(\beta)$. Then, unless (d) $\len(\beta)\geq h$, the following hold:

-   there is a bipolar dual subgraph $\delta_1$ (“induced” by $\delta$) in $(H\cutt \alpha)^*$;

-   there exists a closed walk in $(H\cutt \alpha)^*$ that is odd-leaping $\delta_1$; and

-   the shortest $\delta_1$-polarity switching ear in $(H\cutt \alpha)^*$ has length $h_1\geq h-\frac12\len(\alpha)$.

Conditions (a) and (a’) address the “preservation of $\gamma$” requisite from Lemma \[lem:kl-to-stretch\], and (c),(c’) address the necessarily long “switching distance”. Conditions (b) and (b’) have a purely technical purpose. Notice, for instance, that if (b) is true, then the embedding $H$ is not planar (and so the stretch of $H$ is well defined). Indeed, a closed walk odd-leaping a bipolar plane $\delta$ cannot exist since such a $\delta$ would equal its $H^*$-induced embedding $\tilde\delta$, which means that $\delta$ is face-bicolored, too; a simple parity argument then gives a contradiction. For a similar parity reason, (b) implies that a $\delta$-polarity switching ear in $H^*$ (implicitly required in (c)) must exist. Moreover, as we proceed in the cutting process, the non-planarity implied by (b’) guarantees that we will eventually arrive at the desired exceptional conclusion (d) $\len(\beta)\geq h$, which is the ultimately desired outcome for Lemma \[lem:cutstep\].

Recall the definition of cutting an embedding $H$ along a dual cycle $\alpha$. The dual graph $H^*\cutt\alpha=(H\cutt\alpha)^*$ is obtained from $H^*$ by successive contractions of all the dual edges in $E(\alpha)$ into one dual vertex $a$, and then “splitting” $a$ into two $a_1,a_2$ (giving the two $\alpha$-cut faces of $H\cutt\alpha$). This “stepwise contraction” perspective of cutting turns out to be very useful in our proof.

[*Proof of (a’)*]{}. Let $\varepsilon$ denote the subgraph of $H_1^*$ induced by the edges in $E(\delta)\sem E(\alpha)$. If $\alpha=\delta$, then clearly (d) $\len(\beta)\geq h$, and so we may assume that $\varepsilon$ is nonempty. We show that we can choose $\delta_1=\varepsilon$, under the assumption that $\alpha$ contains a $\delta$-polarity switching ear (the validity of this assumption follows since, if no such switching ear existed, then by (c) it would follow that $\len(\beta)\geq\len(\alpha)\geq h$, thus implying (d)).

The following is immediate from the definition of bipolarity:

\[factA\] If $f\in E(H^*)$ is not a loop-edge and not a $\delta$-polarity switching ear, then the dual graph $H^*\contract f$ (obtained by [*contraction*]{} of $f$) is embedded in the same surface as $H^*$, and the dual subgraph $\delta'$ induced by $E(\delta)\sem\{f\}$ in $H^*\contract f\>$ is bipolar again, where the $\delta'$-polarities are naturally inherited from the $\delta$-polarities.

Since we assume that $\alpha$ contains no $\delta$-polarity switching ear, we can iteratively apply Fact \[factA\] to all edges of $\alpha$ except some (the last one) $f_1\in E(\alpha)\sem E(\beta)$. In this way we get an “intermediate” embedding $H_1^*=H^*\contract\big(E(\alpha)\!\sem\!\{f_1\}\big)$ such that $f_1$ is a nonseparating dual loop-edge in $H_1^*$, and bipolar $\varepsilon_1\subseteq H_1^*$ is naturally derived from $\delta$. Let $a$ be the face of $H_1$ that is the double end of $f_1$, and let the $H_1^*$-rotation of edges around $a$ be $e_1,\dots,e_i,f_1,e_1',\dots,e_j',f_1$. The last step in the construction of $H_1^*$ (and of $\varepsilon$) is to remove $f_1$ and split $a$ into $a_1,a_2$ such that the $H_1^*$-rotation around $a_1$ (respectively, $a_2$) is $e_1,\dots,e_i$ (respectively, $e_1',\dots,e_j'$).

Clearly, $\varepsilon_1=\varepsilon$ stays bipolar in $H_1^*$ if $a\not\in V(\varepsilon_1)$, and so we assume $a\in V(\varepsilon_1)$. Let $\tilde\varepsilon$ denote the $H_1^*$-induced embedding of $\varepsilon$. Let $e_a$ and $e_b$ be the first and last element of the list $e_1,\ldots,e_i$, respectively, that are also edges of $\varepsilon$. Note that both ends of $f_1$ in the $H_1^*$-rotation around $a$ are between $e_b$ and $e_a$. Then, $e_b,e_a$ appear consecutively on a unique face $x$ of $\tilde\varepsilon$. Analogously, we find a face $x'$ at $a_2$ in $\tilde\varepsilon$. Loosely speaking, $x,x'$ are the dual $\tilde\varepsilon$-faces “inheriting” the two $H_1^*$-faces incident with $f_1$. If $f_1\not\in E(\varepsilon_1)$, then both halfedges of $f_1$ are of the same $\varepsilon_1$-polarity (by our assumption on $\alpha$), say positive. Hence both $\tilde\varepsilon$-faces $x$ and $x'$ will get (consistently) positive polarity, and so $\varepsilon$ is bipolar in $H_1^*$. If, on the other hand, $f_1\in E(\varepsilon_1)$, then one of the two faces incident with $f_1$ in the $H_1^*$-induced embedding $\tilde\varepsilon_1$ of $\varepsilon_1$ is positive, say the one containing edge(s) from $e_1,\dots,e_i$, and the other one is negative. Then the $\tilde\varepsilon$-face $x$ will be (consistently) positive and $x'$ negative. Thus also in this case $\varepsilon=\delta_1$ is bipolar in $H_1^*$.

[*Proof of (b’)*]{}. As in (a’), we may assume that $\alpha$ contains no $\delta$-polarity switching ear. We can make a similar assumption with $\beta$: if there is a $\delta$-polarity switching ear contained in $\beta$, then $\len(\beta)\geq h$ (that is, (d) holds). The following counterpart of Fact \[factA\], formulated for any closed dual walk $\psi$ in $H^*$, is easily derived from our definition of a leap.

\[factB\] Suppose $f\in E(H^*)$ is not a loop-edge and not a $\delta$-polarity switching ear, and denote by $\delta'$, $\psi'$ the dual subgraphs induced by $E(\delta)\sem\{f\}$ and $E(\psi)\sem\{f\}$ in $H^*\contract f$ (i.e., after contraction of $f$). Then the number of leaps of $\delta'$ and $\psi'$ in $H^*\contract f$ is the same as the number of leaps of $\delta$ and $\psi$ in $H^*$, with an exception when $f\in E(\psi)\sem E(\delta)$ and both ends of $f$ are incident with leaps of $\delta$ and $\psi$ in $H^*$ (in which case the two leaps vanish in $H^*\contract f$).

We now proceed in the same way as in (a’), and use the same notation $H_1^*,$ $f_1,a,$ $\varepsilon_1$, etc. Let $\omega$ be a dual closed walk in $H^*$ odd-leaping $\delta$, and $\omega_1$, $\beta_1$ denote the dual closed walks in $H_1^*$ induced by $E(\omega)\cap E(H_1^*)$ and $E(\beta)\cap E(H_1^*)$. By an iterative application of Fact \[factB\] to all edges in $E(\alpha)\sem\{f_1\}$, we get that the parity of leaping between $\delta$ and $\omega$ (respectively, $\delta$ and $\beta$) in $H^*$ is the same as that between $\varepsilon_1$ and $\omega_1$ (respectively, $\varepsilon_1$ and $\beta_1$) in $H_1^*$. Hence $\omega_1$ is odd-leaping $\varepsilon_1$, and $\beta_1$ is even-leaping $\varepsilon_1$, since $\beta$ contains no $\delta$-polarity switching ear in $H^*$ and so $\beta$ is not odd-leaping $\delta$.

We note that $a\in V(\beta_1)$ since $\alpha$ intersects $\beta$, and recall $f_1\not\in E(\beta)$. If $f_1\in E(\omega)$, then we moreover remove $f_1$ from $\omega_1$; this does not change the parity of leaping between $\varepsilon_1$ and $\omega_1$. We say that the dual walk $\omega_1$ [*passes through*]{} $a$ in $H_1^*$ if one edge of $\omega_1$ is from $e_1,\dots,e_i$ and the next edge of $\omega_1$ is among $e_1',\dots,e_j'$, or vice versa. Every time $\omega_1$ passes through $a$, we replace this pass by one iteration of the cycle $\beta_1$. The resulting closed dual walk $\omega_2$ in $H_1^*$ (which does not pass through $a$) is again odd-leaping $\varepsilon_1$, since $\beta_1$ is even-leaping $\varepsilon_1$. Then, the subgraph $\omega_0$ induced by $E(\omega_2)$ in the graph $H_1^*$ is a closed dual walk odd-leaping $\varepsilon=\delta_1$.

[*Proof of (c’)*]{}. Let $\sigma$ be a $\delta_1$-polarity switching ear in $H_1^*$ of length $h_1$. If $V(\sigma)$ contains both $\alpha$-cut faces $a_1,a_2$, then the lift $\hat\nu$ of a subpath $\nu\subseteq\sigma$ between $a_1$ and $a_2$ is a $\delta$-polarity switching ear, and hence $h\leq\len(\hat\nu)\leq h_1$, thus implying (c’). Otherwise, the lift $\hat\sigma$ in $H^*$ is an $(\alpha\cup\delta)$-ear which means that, for some subpath $\pi\subseteq\alpha$ of length at most $\frac12\len(\alpha)$ (possibly empty), $\hat\sigma\cup\pi$ is a $\delta$-ear. Since $\sigma$ is $\delta_1$-polarity switching in $H_1^*$, and the $\delta_1$-polarities are inherited from those of $\delta$ in $H^*$ by (a’) and Fact \[factA\], we conclude that $\hat\sigma\cup\pi$ is a $\delta$-polarity switching ear. Therefore, $h\leq\len(\hat\sigma\cup\pi)\leq h_1+\frac12\len(\alpha)$ as claimed.

Proof of Lemma \[lem:kl-to-stretch\]
------------------------------------

We proceed by induction, using Lemma \[lem:cutstep\]. Notice that all the conditions (a),(b),(c) of Lemma \[lem:cutstep\] are satisfied by the graph $H$, its bipolar dual cycle $\delta:=\gamma$, and by $h:=\ell$. Let $H_0=H$, $\gamma_0=\gamma$, and $\ell_0=\ell$. Until we reach the condition (d) $\len(\beta)\geq h$, we repeatedly apply Lemma \[lem:cutstep\] for $i=1,2,\dots$ to $H:=H_{i-1}$ and $\delta:=\gamma_{i-1},\, h:=\ell_{i-1}$, obtaining $H_{i}:=H\cutt\alpha$ and $\gamma_{i}:=\delta_1,\, \ell_i:=h_1$. After the maximum possible number $i$ of iterations in which (d) does not hold:

-   the graph $H_i$ has genus $g-i$, and it is $i\leq g-1$ since (b’) implies nonplanarity of $H_i$;

-   the nonseparating dual edge-width is $\ewnd(H_i)\geq2^{-i}\cdot\ewnd(H)>1$ (this follows by iterating Lemma \[lem:cutdew\] $i$ times); and

-   the shortest $\gamma_i$-polarity switching ear in $H_i^*$ has length at least $\ell_i\geq 2^{-i}\cdot\ell$, since one can iterate $h_1\geq h-\frac12\len(\alpha)\geq h-\frac12\len(\beta)\geq \frac12h$ at each of the $i$ steps.

Hence (as no further iteration is possible), we have gotten an $i\leq g-1$ such that (cf. Lemma \[lem:cutstep\]) there exists a pair of odd-leaping dual cycles $\alpha_i,\beta_i$ in $H_i^*$ such that $\stretchd(H_i)=\len(\alpha_i)\cdot\len(\beta_i)$, and (d) $\len(\beta_i)\geq \ell_i$ holds. Consequently, $$\stretchd(H_i)=\len(\alpha_i)\cdot\len(\beta_i)\geq
    \ewnd(H_i)\cdot \ell_i\geq 2^{-i}\ewnd(H)\cdot2^{-i}\ell
    = 2^{-2i}\cdot k\ell
\,.$$ By setting $H'=H_i$ for $g'=g-i$, Lemma \[lem:kl-to-stretch\] follows.

Concluding remarks {#sec:concluding}
==================

There are several natural questions that arise.

#### Extension to nonorientable surfaces.

One can wonder whether our results, namely about approximating planar crossing number of an embedded graph, can also be extended to nonorientable surfaces of higher genus. Indeed, the upper-bound result of [@BPT06] holds for any surface, and there is an algorithm to approximate the crossing number for graphs embeddable in the projective plane [@GHLS08]. We currently do not see any reason why such an extension would be impossible.

However, the individual steps become much more difficult to analyze and tie together, since the “cheapest” cut through the embedding can cut (a) a handle along a two-sided loop, (b) an antihandle along a two-sided loop, or (c) a crosscap along a one-sided loop. Hence it then does not suffice to consider toroidal grids as the sole base case (and a usable definition of “nonorientable stretch” should reflect this), but the lower bound may also arise from a projective or Klein-bottle grid minor. Already for the latter, there are currently no non-trivial results known. We thus leave this direction for future investigation.

#### Dependency of the constants in Theorem \[thm:main-overview\] on $\Delta$ and $g$.

Taking a toroidal grid with sufficiently multiplied parallel edges (possibly subdividing them to obtain a simple graph) easily shows that a relation between the toroidal expanse and the crossing number must involve a factor of $\Delta^2$. Regarding an efficient approximation algorithm for the crossing number, general dependency on the maximum degree seems unavoidable as well, as is suggested by comparison with related algorithmic results. However, considering the so-called minor crossing number (see Section \[sec:minorcr\] below), one can avoid this dependency at least in a special case.

The exponential dependency of the constants and the approximation ratio on $g$, on the other hand, is very interesting. It pops up independently in multiple places within the proofs, and these occurrences seem unavoidable on a local scale, when considering each inductive step independently. However, it seems very hard to construct any example where such an exponential jump or decrease can actually be observed. It might be that a different approach with a global view can reduce the dependency in Theorem \[thm:main-overview\] to some $\mathit{poly}(g)$ factor, cf. also [@DV12].

Toroidal grids and minor crossing number {#sec:facestretch}
----------------------------------------

\[sec:minorcr\] The *minor crossing number* $\mcr(G)$ [@BFM06] is the smallest crossing number over all graphs $H$ that have $G$ as their minor. Hence it is, by definition and in contrast to the traditional crossing number, a well-behaved minor-monotone parameter. In general, however, minor crossing number is not any easier to compute [@Hl06] than ordinary crossing number. We note the following intuitive observation related to our topic: if $G$ is embedded in $\Sigma$ with face-width $r$, then $G$ is a surface minor of a graph $H$ (in particular, $H$ is embedded in $\Sigma$ as well) such that $\ewn(H)=r$. Indeed, consider a loop $\lambda$ in $\Sigma$ attaining $\fw(G)$ and split every vertex intersected by $\lambda$ into an edge “perpendicular” to $\lambda$. This results in desired $H$ (for formal details, see the proof of Lemma \[lem:cr-fstretch-torus\]).

For an embedded graph $G$, let $G_f$ denote the vertex-face incidence (bipartite) graph of $G$. It is well-known that $\fw(G)=\frac12\ew(G_f)$. We can analogously define the [*face stretch*]{} of an embedded graph $G$ as $\stretchf(G)=\frac14\stretch(G_f)$, and claim:

\[lem:cr-fstretch-torus\] Let $G$ be a graph embedded in an orientable surface $\Sigma$. Then there is a graph $H$ also embedded in $\Sigma$, such that $G$ is a minor of $H$ and $$\stretchd(H)\leq \stretchf(G)+\sqrt{\stretchf(G)} .$$

Let $A,B$ be one-leaping cycles of $G_f$ witnessing $\stretchf(G)$. When viewing $A$ and $B$ as simple loops $\alpha$ and $\beta$, respectively, on the surface $\Sigma$, they intersect the embedding of $G$ only in $a=\len(A)/2$ and $b=\len(B)/2$ vertex points. Consider a vertex $v$ of $G$ intersected by $\alpha$. We replace $v$ in the embedding with two new vertices $v_l,v_r$, where $v_l$ is incident with those edges of $v$ on the left-hand side of $\alpha$ and $v_r$ with the edges of $v$ on the right-hand side of $\alpha$. We join $v_l$ to $v_r$ with a new edge; it is “perpendicular” to $\alpha$ in the embedding in $\Sigma$ (Figure \[fig:fstr-split\]). Let $H_0$ be the new graph having $G$ as its minor. If $v$ belongs also to $\beta$, and there is an edge (or two) of $E(B)\sem E(A)$ in $G_f$ incident to $v$, then we position the corresponding one (or two) of $v_l,v_r$ right on this section of $\beta$ close to original $v$. So, $\beta$ intersects the embedded graph $H_0$ only in vertex points, as well. We apply the same construction to the vertices of $H_0$ intersected by $\beta$, resulting in the desired embedded graph $H$ having $G$ as its minor.

In $H$, the loop $\alpha$ now intersects exactly $a$ edges (and no vertex), while the loop $\beta$ intersects $b$ or $b+1$ edges. The latter case happens when $\alpha,\beta$ intersect each other in exactly one vertex point $v$ of $G$, and hence both $v_l,v_r$ belong to $\beta$ in $H'$. (Generally, this odd case is unavoidable in the situation illustrated in Figure \[fig:fstr-split\].) Therefore, up to symmetry between $\alpha,\beta$, $H$ witnesses that $\stretchd(H)\leq\min\{a(b+1),b(a+1)\}= ab+\min(a,b)\leq ab+\sqrt{ab}$, where $\stretchf(G)=ab$.

From Lemma \[lem:cr-stretch-torus\] we then immediately obtain:

\[cor:cr-fstretch-torus\] If $G$ is a graph embedded in the torus, then $\mcr(G)\leq\stretchf(G)+\sqrt{\stretchf(G)}$. Assuming $\fw(G)\geq5$, we have $\mcr(G)\leq\frac65\stretchf(G)$.

The next logical step is to translate the findings from Section \[sub:toridalexp\] to the face stretch notion. In the special case of the torus, this translation in fact makes some things simpler. Consider a graph embedded in the torus $\Sigma_1$. Let $\alpha$ be a loop in $\Sigma_1$ intersecting $G$ only in vertex points. When cutting along $\alpha$ we obtain a cylindrical surface $\Gamma$ with two borders, corresponding to the former left and right-hand sides of $\alpha$. We naturally obtain the graph $G'$ embedded on $\Gamma$ from $G$ by duplicating the vertices $v$ cut by $\alpha$ along the two borders. As in the previous proof, each copy of $v$ in $G'$ retains the edges formerly incident to $v$ on the respective side of $\alpha$ on $\Sigma_1$. We say that $G'$ embedded in $\Gamma$ is obtained by [*cutting $G$ along $\alpha$*]{}.

\[thm:facegrid-torus\] Let $G$ be a graph embedded in the torus $\Sigma_1$ with $k:=\fw(G)$. Let $\alpha$ be a loop in $\Sigma_1$ witnessing the face-width of $G$, and let $G'$ be a graph embedded in the cylinder $\Gamma$, obtained by cutting $G$ along $\alpha$. Among all pairs of points $x,y$ on the opposite bounderies of $\Gamma$, let $\ell$ be the least number of points in which a simple arc from $x$ to $y$ in $\Gamma$ intersects $G'$, not counting $x,y$ themselves. If $k\geq5$, then $G$ contains a toroidal $\floor{2k/3} \times \ell\>$-grid as a minor.

Analogously to Claim \[cl:ellcycles\] we prove that $G$ has a set of at least $\ell$ pairwise disjoint cycles, all homotopic to $\alpha$ in $\Sigma_1$. Then we finish as in the proof of Theorem \[thm:agrid-torus\], using Theorems \[thm:deGS\] and \[thm:two-cycle-families\].

\[lem:stretch-kl-torus\] Let $G$, $k\geq5$, and $\ell$ be as in Theorem \[thm:facegrid-torus\]. Then $\stretchf(G)\leq3k\ell$.

The proof is analogous to that of Lemma \[lem:thstr\], but slightly more complicated. Let $\gamma'$ be the curve in $\Gamma$ defining $\ell$ as above, and let $\gamma$ denote the corresponding curve back in $G$ in $\Sigma_1$. We can consider $\alpha$ and $\gamma$ as a cycle and a path, respectively, in the vertex-face incidence graph $G_f$. Let $\alpha\cap\gamma=\{a,b\}$ (where possibly $a=b$), and let $\alpha'$ denote the component of $\alpha\sem\{a,b\}$ having not more intersecting points with the drawing $G$ than the other component. Then $\alpha'\cup\gamma$ is a noncontractible loop intersecting $G$ in $\ell'\leq\ell+k/2+1$ points, as a simple case analysis shows (observe that, indeed, $\ell'$ may be larger than $\ell+k/2$ when some of $a,b$ are vertices of $G$). In particular, $\ell'\geq k\geq5$ and so $k/2\leq\ell+1$ and $\ell\geq2$. Therefore, $\alpha$ and $\alpha'\cup\gamma$ define a pair of one-leaping cycles in $G_f$ witnessing $\stretchf(G)\leq k\ell'\leq3k\ell$.

We may now conclude, in the toroidal case:

\[thm:main-minorcr\] Let $G$ be a graph embedded in the torus. If $\fw(G)\geq5$, then

-   $\frac{10}{63}\cdot\mcr(G) \leq \Tex(G) \leq 12\cdot\mcr(G)$, and

-   there is a polynomial time algorithm that computes a graph $H$ having $G$ as its minor and outputs a drawing of $H$ in the plane with at most $76\cdot\mcr(G)$ crossings.

Let $G$, $k\geq5$, and $\ell$ be as in Theorem \[thm:facegrid-torus\]. Combining Corollary \[cor:cr-fstretch-torus\] with Lemma \[lem:stretch-kl-torus\] we get $\mcr(G)\leq\frac{18}5k\ell$. Then, Theorem \[thm:facegrid-torus\] gives $\Tex(G)\geq\floor{2k/3}\cdot\ell\geq\frac47k\ell$ and the left-hand side of (a) follows. For the right-hand side, we simply use the fact that $\Tex(G)$ is minor monotone and apply Corollary \[cor:crossing-texp\] to the graph witnessing $\mcr(G)$.

For (b) we compute the graph $H$ from Lemma \[lem:cr-fstretch-torus\] and apply the algorithm of Theorem \[thm:main-overview\]. The resulting drawing of $H$ has at most $\frac{18}5k\ell$ crossings by the previous, and $\mcr(G)\geq\frac1{12}\cdot\frac47k\ell=\frac1{21}k\ell$. Hence the number of crossings in $H$ is at most $21\cdot\frac{18}5\mcr(G)\leq76\mcr(G)$.

Obviously, the approximation constants in Theorem \[thm:main-minorcr\] are very rough and can likely be improved a lot. However, the important point is that these constants are independent of the maximum degree. It is interesting to ask whether Theorem \[thm:main-minorcr\] can be extended to all orientable surfaces analogously to Theorem \[thm:main-overview\]. Although this seems quite plausible, there are complications similar to those seen already in the proofs of Lemmas \[lem:cr-fstretch-torus\] and \[lem:stretch-kl-torus\]. Consequently, the nice technical properties of stretch presented in Section \[sec:more\] cannot be straighforwardly extended to face stretch, and the whole question is left for future research.

Removing the density requirement {#sec:nodensity}
--------------------------------

Our algorithmic technique in Section \[sec:drawing-upper\] starts with a graph on a higher surface, and brings the graph to the plane without introducing too many crossings. As mentioned before, focusing only on surface-operations will inevitably require a certain lower bound on the density of the original embedding. However, we can naturally combine this algorithm with some other algorithmic results on inserting a *small* number of edges into a planar graph, to obtain a polynomial algorithm with essentially the same approximation ratio but without the density requirement. This combination of algorithms can be sketched as follows:

1.  As long as the embedding density requirement of Theorem \[thm:main-overview\] is violated, we cut the surface along the violating loops. Let $K\subseteq E(G)$ be the set of edges affected by this; we know that $|K|$ is small, bounded by a function of $g$ and $\Delta$. Let $G_K:=G-K$.

2.  By Theorem \[thm:upper-cr\], applied to $G_K$, we obtain a suitable set $F\subseteq E(G_K)$ such that $G_{KF}:=G_K-F$ is plane. ($F$ is the union of the edge sets corresponding to dual cycles in the considered dual planarizing sequence of $G_K$.)

3.  We would like to apply independently [@MR2874100] to insert the edges of $K$ back to $G_{KF}$ with not many crossings, and Theorem \[thm:upper-cr\] to insert $F$ back to $G_{KF}$. The number of possible mutual crossing $|F|\cdot|K|$ is neglectable, but the real trouble is that [@MR2874100] is allowed to change the planar embedding of $G_{KF}$ and hence the insertion routes assumed by Theorem \[thm:upper-cr\] may no longer exist. Fortunately, the number of the insertion routes for $F$ is bounded in the genus (unlike $|F|$), and so the algorithm from [@MR2874100] can be adapted to respect these routes without a big impact on its approximation ratio.

Unfortunately, turning this simple sketch into a formal proof would not be short, due to the necessity to bring up many fine algorithmic details from [@MR2874100]. That is why we consider another option, allowing short self-contained proof at the expense of giving a weaker approximation guarantee. We use the following simplified formulation of the main result of [@MR2874100]. For a graph $H$ and a set of edges $K$ with ends in $V(H)$, but $K\cap
E(H)=\emptyset$, let $H+K$ denote the graph obtained by adding the edges $K$ into $H$.

\[thm:apxmei\] Let $H$ be a connected planar graph with maximum degree $\Delta$, $K$ an edge set with ends in $V(H)$ but $K\cap E(G)=\emptyset$, and $k=|K|$. There is a polynomial-time algorithm that finds a drawing of $H+K$ in the plane with at most $d\cdot\crg(H+K)$ crossings, where $d$ is a constant depending only on $\Delta$ and $k$. In this drawing, subgraph $H$ is drawn planarly, i.e., all crossings involve at least one edge of $K$.

An algorithmic strengthening of our Theorem \[thm:main-overview\] now reads:

\[thm:main-nodense\] Let $\Sigma$ be an orientable surface of fixed genus $g>0$, and let $\Delta$ be an integer constant. Assume $G$ is a graph of maximum degree $\Delta$ embedded in $\Sigma$. There is a polynomial time algorithm that outputs a drawing of $G$ in the plane with at most $c_3\cdot\crg(G)$ crossings, where $c_3$ is a constant depending on $g$ and $\Delta$.

Let $r_0,c_2$ be the constants from Theorem \[thm:main-overview\], depending on $g$ and $\Delta$. Recall that $r_0$ is nondecreasing in $g$, and so we may just fix it for the rest of the proof. If $\ewnd(G)<r_0\deee$, let $\gamma$ be the witnessing dual cycle of $G$. We cut $G$ along $\gamma$, and repeat this operation until we arrive at an embedded graph $G_K\subseteq G$ of genus $g_K<g$ such that $\ewnd(G_K)\geq r_0\deee$ (and hence $\fw(G_1)\geq r_0$). Let $K=E(G)\sem E(G_K)$ be the affected edges, where $|K|\leq g\,r_0\deee$ is bounded by a constant.

If $g_K=0$, then we simply finish by applying Theorem \[thm:apxmei\]. Otherwise, we apply the algorithm of Theorem \[thm:upper-cr\] to $G_K$, which results in a planar graph $G_{KF}\subseteq G_K$ and the edge set $F=E(G_K)\sem E(G_{KF})$, such that $F$ can be drawn into $G_{KF}$ using at most $c_2\cdot\crg(G_K)$ crossings by Theorem \[thm:main-overview\]. In this resulting drawing of $G_K$ we replace each crossing by a new subdividing vertex. This gives a planarly embedded graph $G_K'$ that contains a planarly embedded subdivision $G_{KF}'$ of $G_{KF}$. Let $F_2=E(G_K')\sem E(G_{KF}')$. Since we clearly may assume that every edge of $F$ required at least one crossing in $G_{KF}$, we have $|F_2|\leq2c_2\cdot\crg(G_K)$. Now we apply Theorem \[thm:apxmei\] to $H=G_{KF}'$ and $K$ (from the previous paragraph). This gives a drawing $G_F$ of $G_{KF}'+K$ with at most $d\cdot\crg(G_{KF}+K)$ crossings in the plane. The final task is to put back the edges of $F_2$ into $G_F$; note, however, that the planar subdrawing of $G_{KF}'$ within $G_F$ is generally different from the original embedding of $G_{KF}'$.

For the latter task use the following technical claim:

\[cl:edgeback\] Suppose $H$ is a connected graph embedded in the plane, and $e,f\not\in E(H)$ are two edges joining vertices of $H$ such that $H+f$ is a planar graph. If $e$ can be drawn in $H$ with $\ell$ crossings, then there is a planar embedding of $H+f$ in which $e$ can be drawn with at most $\ell+2\cdot\lfloor\Delta(H)/2\rfloor$ crossings.

Although [@HS06] does not explicitly handle the algorithmic aspect of Claim \[cl:edgeback\], it is easily seen there that the claimed drawing of $H+f+e$ can be found in polynomial time from the assumed drawing of $H+e$ (for the algorithm of [@MR2874100], for example, this is a simple special case).

Let $F_2=\{f_1,f_2,\dots,f_a\}$. By induction on $i=1,2,\dots,a$, we apply Claim \[cl:edgeback\] to $f:=f_i$ and $H:=G_{KF}'+f_1+\dots+f_{i-1}$, and simultaneously to each $e$ from $K$. As the final result we obtain a planar embedding of $G_{KF}'+F_2=G_K'$. Into this $G_K'$, we can draw $K$ with at most $|K|\cdot2\deee\cdot|F_2|+|K|^2/2$ additional crossings (compared to the number of crossings achieved by Theorem \[thm:apxmei\] to draw $K$ into $G_K$). By turning the vertices of $V(G_K')\sem V(G_K)$ back into edge crossings of $G_K$ this leads to a drawing of $G_K+K=G$ with at most $$\begin{aligned}
   c_2\cdot\crg(G_K) + 
   d\cdot\crg(G_{KF}+K) &+
   |K|\cdot2\deee |F_2|
    +|K|^2/2 \\
   \leq c_2\cdot\crg(G_K) + 
   d\cdot\crg(G_{KF}+K) &+
   g\,r_0\Delta^2c_2\cdot\crg(G_K)
    +(g\,r_0\Delta)^2/8\\
   \leq (c_2 + 
   d &+
   g\,r_0\Delta^2c_2)\cdot\crg(G)
    +(g\,r_0\Delta)^2/8\end{aligned}$$ crossings where all the remaining terms are constants depending only on $g$ and $\Delta$.

[99]{}

[^1]: Faculty of Mathematics/Computer Science, Osnabrück University. Osnabrück, Germany.

[^2]: Faculty of Informatics, Masaryk University. Brno, Czech Republic. Supported by the Czech Science Foundation, Eurocores project GraDR GIG/11/E023, and project 14-03501S (since 2014).

[^3]: Instituto de Fisica, Universidad Autonoma de San Luis Potosi. San Luis Potosi, Mexico. Supported by CONACYT Grant 106432.

[^4]: This draws upon and extends partial results presented at ISAAC 2007 [@HS07] and SODA 2010 [@HC10].

[^5]: Note that this quantity is also called the “crossing number” of the curves, and a pair of curves may be said to be “$k$-crossing”. Such a terminology would, however, conflict with the graph crossing number, and we have to avoid it. Following [@HC10], we thus use the term “$k$-leaping”, instead.
