Genus, Treewidth, and Local Crossing Number

Abstract

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth $O(\sqrt{(g+1)(k+1)n})$ and layered treewidth $O((g+1)k)$, and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth $O(\sqrt{(k+1)n})$ and layered treewidth $O(k+1)$, which are tight bounds that improve a previously known $O((k+1)^{3/4}n^{1/2})$ treewidth bound. Additionally, we show that for $g<m$, every m-edge graph can be embedded on a surface of genus g with $O((m/(g+1))\log ^2 g)$ crossings per edge, which is tight to a polylogarithmic factor.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Treewidth is a graph parameter that measures how similar a graph is to a tree. It is a key measure of the complexity of a graph and is of fundamental importance in algorithmic graph theory and structural graph theory, especially in Robertson and Seymour’s graph minors project. Treewidth is closely related to the size of a smallest separator, a set of vertices whose removal splits the graph into connected components of at most $\frac{2n}{3}$ vertices, where n (as always) is the number of vertices in the graph. Graphs of low treewidth necessarily have small separators, and graphs in which every subgraph has a small separator have low treewidth [1, 2]. See Sect. 2 for a detailed definition of treewidth.

A graph is k-planar if it can be drawn in the plane with at most k crossings on each edge. The local crossing number of the graph is the minimum k for which it is k-planar [3, pages 51–53]. An important example is the $p\times q\times r$ grid graph, with vertex set $[p]\times [q]\times [r]$ and all edges of the form $(x,y,z)(x+1,y,z)$ or $(x,y,z)(x,y+1,z)$ or $(x,y,z)(x,y,z+1)$. A suitable linear projection from the natural three-dimensional embedding of this graph to the plane gives a $(r-1)$-planar drawing, as illustrated in Fig. 1.

Fig. 1.

The $p\times q\times r$ grid graph is $(r-1)$-planar.

The starting point for our work is the following question: what is the maximum treewidth of k-planar graphs? Grigoriev and Bodlaender [4] studied this question and proved an upper bound of $O(k^{3/4}n^{1/2})$. We improve this and give the following tight bound:

Theorem 1

The maximum treewidth of k-planar n-vertex graphs is

$$\begin{aligned} \varTheta \left( \min \left\{ n,\sqrt{(k+1)n}\right\} \right) . \end{aligned}$$

More generally, define a graph to be (g, k)-planar if it can be drawn in a surface of Euler genus at most g with at most k crossings on each edge.¹ For instance, Guy et al. [5] investigated the local crossing number of toroidal embeddings—in this notation, the (2, k)-planar graphs. We again determine an optimal bound on the treewidth of such graphs.

Theorem 2

The maximum treewidth of (g, k)-planar n-vertex graphs is

$$\begin{aligned} \varTheta \left( \min \left\{ n,\sqrt{(g+1)(k+1)n}\right\} \right) . \end{aligned}$$

In both these theorems, the $k=0$ case (with no crossings) is well known [6]. We prove our upper bounds by using the concept of layered treewidth [7], and we prove matching lower bounds by finding (g, k)-planar graphs without large separators and using the known relations between separator size and treewidth.

Finally, we study the (g, k)-planarity of graphs as a function of their number of edges. For (global) crossing number, it is known that a graph with n vertices and m edges drawn on a surface of genus g (sufficiently small with respect to m) may require $\varOmega (\min \{m^2/g,m^2/n\})$ crossings, and it can be drawn with $O((m^2\log ^2 g)/g)$ crossings [8]. In particular, the lower bound implies that some graphs require $\varOmega (m/g)$ crossings per edge on average, and therefore also in the worst case. We prove a nearly-matching upper bound:

Theorem 3

For every graph G with m edges, for every integer $g\geqslant 1$, there is a drawing of G in the orientable surface with at most g handles and with

$$\begin{aligned} O\left( \frac{m\log ^2 g}{g}\right) \end{aligned}$$

crossings per edge.

2 Background

For $\epsilon \in (0,1)$, a set S of vertices in a graph G is an $\epsilon$ -separator of G if each component of $G-S$ has at most $\epsilon |V(G)|$ vertices. It is conventional to set $\epsilon =2/3$ but the precise choice makes no difference to the asymptotic size of a separator.

A tree-decomposition of a graph G is given by a tree T whose nodes index a collection $(B_x\subseteq V(G):x\in V(T))$ of sets of vertices in G called bags, such that:

• For every edge vw of G, some bag $B_x$ contains both v and w, and

• For every vertex v of G, the set $\{x\in V(T):v\in B_x\}$ induces a non-empty (connected) subtree of T.

The width of a tree-decomposition is $\max _x |B_x|-1$, and the treewidth ${{\mathrm{tw}}}(G)$ of a graph G is the minimum width of any tree decomposition of G. Treewidth was introduced (with a different but equivalent definition) by Halin [9] and tree decompositions were introduced by Robertson and Seymour [10] who proved:

Lemma 1

[10]. Every graph with treewidth k has a $\frac{1}{2}$-separator of size at most $k+1$.

The notion of layered tree decompositions is a key tool in proving our main theorems. A layering of a graph G is a partition $(V_0,V_1,\dots ,V_t)$ of V(G) such that for every edge $vw\in E(G)$, if $v\in V_i$ and $w\in V_j$, then $|i-j|\leqslant 1$. Each set $V_i$ is called a layer. For example, for a vertex r of a connected graph G, if $V_i$ is the set of vertices at distance i from r, then $(V_0,V_1,\dots )$ is a layering of G, called the bfs layering of G starting from r. A bfs tree of G rooted at r is a spanning tree of G such that for every vertex v of G, the distance between v and r in G equals the distance between v and r in T. Thus, if $v\in V_i$ then the vr-path in T contains exactly one vertex from layer $V_j$ for $0\leqslant j\leqslant i$.

The layered width of a tree-decomposition $(B_x:x\in V(T))$ of a graph G is the minimum integer $\ell$ such that, for some layering $(V_0,V_1,\dots ,V_t)$ of G, each bag $B_x$ contains at most $\ell$ vertices in each layer $V_i$. The layered treewidth of a graph G is the minimum layered width of a tree-decomposition of G. Note that if we only consider the trivial layering in which all vertices belong to one layer, then layered treewidth equals treewidth plus 1.

Dujmović, Morin, and Wood [7] introduced layered treewidth and proved the following results, where a graph G is apex if $G-v$ is planar for some vertex v:

Theorem 4

(Dujmović, Morin, and Wood [7]).

• (a) Every planar graph has layered treewidth at most 3.

• (b) Every graph with Euler genus g has layered treewidth at most $2g+3$.

• (c) For every apex graph H, there is a number c such that every H-minor-free graph has layered treewidth at most c.

• (d) If a minor-closed class has bounded layered treewidth, then it excludes a fixed apex graph as a minor.

The same characterization by forbidden apex minors was previously known for minor-closed classes of bounded local treewidth [11], establishing the equivalence of bounded local treewidth and bounded layered treewidth in minor-closed classes; however, for families of graphs that are not minor-closed, layered treewidth and local treewidth are distinct. Sergey Norin established the following connection between layered treewidth and treewidth:

Theorem 5

(Norin; see [7]). Every n-vertex graph with layered treewidth k has treewidth at most $2\sqrt{kn}$.

Several results that follow depend on expanders; see [12] for a survey.

Lemma 2

For every $\epsilon \in (0,1)$ there exists $\beta >0$, such that for all $k\geqslant 3$ and $n\geqslant k+1$ (such that n is even if k is odd), there exists a k-regular n-vertex graph H (called an expander) in which every $\epsilon$-separator in H has size at least $\beta n$.

3 k-Planar Graphs

The following is our first contribution.

Theorem 6

Every k-planar graph has layered treewidth at most $6(k+1)$.

Proof

Let G be k-planar; draw G with at most k crossings per edge, and arbitrarily orient each edge of G. Let $G'$ be the graph obtained from G by replacing each crossing by a new degree-4 vertex. Then $G'$ is planar. By Theorem  4(a), $G'$ has layered treewidth at most 3. That is, there is a tree decomposition $T'$ of $G'$, and a layering $V'_0,V_1',\dots$ of $G'$, such that each bag of $T'$ contains at most three vertices in each layer $V'_i$. For each vertex v of $G'$, let $T'_v$ be the subtree of $T'$ formed by the bags that contain v.

Let T be the decomposition of G obtained by replacing each occurrence of a dummy vertex x in a bag of $T'$ by the tails of the two edges that cross at x. We now show that T is a tree-decomposition of G. For each vertex v of G, let $T_v$ be the subgraph of T formed by the bags that contain v. Let $G'_v$ be the subgraph of $G'$ induced by v and the division vertices on the edges for which v is the tail. Then $G'_v$ is connected. Thus $T'_v$, which is precisely the set of bags of $T'$ that intersect $G'_v$, form a (connected) subtree of $T'$. Moreover, for each oriented edge vw of G, if x is the division vertex of vw adjacent to w, then $T'_x$ and $T'_w$ intersect. Since $T_v$ contains $T'_x$, and $T_w$ contains $T'_w$, we have that $T_v$ and $T_w$ intersect. Thus T is a tree-decomposition of G. By construction, each bag of T contains at most six vertices in each layer $V'_i$.

Note that ${{\mathrm{dist}}}_{G'}(v,w)\leqslant k+1$ for each edge vw of G. Thus, if $v\in V'_i$ and $w\in V'_j$ then $|i-j|\leqslant k+1$. Let $V_0$ be the union of the first $k+1$ layers restricted to V(G), let $V_1$ be the union of the second $k+1$ layers restricted to V(G), and so on. That is, for $i\geqslant 0$, let $V_i:=V(G)\cap (V'_{(k+1)i}\cup V'_{(k+1)i+1}\cup \dots \cup V'_{(k+1)(i+1)-1})$. Then $V_0,V_1,\dots$ is a partition of V(G). Moreover, if $v\in V_i$ and $w\in V_j$ for some edge vw of G, then $|i-j|\leqslant 1$. Thus $V_1,V_2,\dots$ is a layering of G. Since each layer in G consists of at most $k+1$ layers in $G'$, the layered treewidth of this decomposition is at most $6(k+1)$.    $\square$

Theorem 4 does not imply Theorem 6, because 1-planar graphs may contain arbitrarily large complete graph minors. For example, the $n\times n\times 2$ grid graph is 1-planar, and contracting the i-th row in the front grid with the i-th column in the back grid gives a $K_n$ minor.

Theorems 5 and 6 imply the upper bound in Theorem 1:

Theorem 7

Every k-planar n-vertex graph has treewidth at most $2\sqrt{6(k+1)n}$.

We now prove the corresponding lower bound.

Theorem 8

For $1\leqslant k\leqslant \frac{3}{2} n$ there is a k-planar graph on n vertices with treewidth at least $c\sqrt{kn}$ for some constant $c>0$.

Proof

Let G be a cubic expander with n vertices. Then G has treewidth at least $\epsilon n$ for some constant $\epsilon >0$ (see for example Grohe and Marx [13]). Consider a straight-line drawing of G. Clearly, each edge is crossed less than $|E(G)|=\frac{3}{2} n$ times. Subdivide each edge of G at most $\frac{3n}{2k}$ times to produce a k-planar graph $G'$ with $n'$ vertices, where $n'\leqslant n +\frac{3n}{2}\,\frac{3n}{2k}<\frac{4n^2}{k}$. Subdivision does not change the treewidth of a graph. Thus $G'$ has treewidth at least $\epsilon n\geqslant \frac{\epsilon }{2}\sqrt{kn'}$.    $\square$

Combining the bound of Theorem 7 with the trivial upper bound ${{\mathrm{tw}}}(G)\leqslant n$ for $k\ge n$ shows that the maximum treewidth of k-planar n-vertex graphs is $\varTheta (\min \{n,\sqrt{kn}\})$ for arbitrary k and n. This completes the proof of Theorem 1.

4 (g, k)-Planar Graphs

Recall that a graph is (g, k)-planar if it can be drawn in a surface of Euler genus at most g with at most k crossings on each edge. The proof method used in Theorem 6 in conjunction with Theorem 4(b) leads to the following theorem.

Theorem 9

Every (g, k)-planar graph G has layered treewidth at most $(4g+6)$ $(k+1)$.

Proof

Consider a drawing of G with at most k crossings per edge on a surface $\Sigma$ of Euler genus g. Arbitrarily orient each edge of G. Let $G'$ be the graph obtained from G by replacing each crossing by a new degree-4 vertex. Then $G'$ is embedded in $\Sigma$ with no crossings, and thus has Euler genus at most g. By Theorem 4(b), $G'$ has layered treewidth at most $2g+3$. That is, there is a tree decomposition $T'$ of $G'$, and a layering $V'_0,V_1',\dots$ of $G'$, such that each bag of $T'$ contains at most $2g+3$ vertices in each layer $V'_i$. For each vertex v of $G'$, let $T'_v$ be the subtree of $T'$ formed by the bags that contain v.

Let T be the decomposition of G obtained by replacing each occurrence of a dummy vertex x in a bag of $T'$ by the tails of the two edges that cross at x. We now show that T is a tree-decomposition of G. For each vertex v of G, let $T_v$ be the subgraph of T formed by the bags that contain v. Let $G'_v$ be the subgraph of $G'$ induced by v and the division vertices on the edges for which v is the tail. Then $G'_v$ is connected. Thus $T'_v$, which is precisely the set of bags of $T'$ that intersect $G'_v$, form a (connected) subtree of $T'$. Moreover, for each oriented edge vw of G, if x is the division vertex of vw adjacent to w, then $T'_x$ and $T'_w$ intersect. Since $T_v$ contains $T'_x$, and $T_w$ contains $T'_w$, we have that $T_v$ and $T_w$ intersect. Thus T is a tree-decomposition of G. By construction, each bag of T contains at most $4g+6$ vertices in each layer $V'_i$.

Note that ${{\mathrm{dist}}}_{G'}(v,w)\leqslant k+1$ for each edge vw of G. Thus, if $v\in V'_i$ and $w\in V'_j$ then $|i-j|\leqslant k+1$. Let $V_0$ be the union of the first $k+1$ layers restricted to V(G), let $V_1$ be the union of the second $k+1$ layers restricted to V(G), and so on. That is, for $i\geqslant 0$, let $V_i:=V(G)\cap (V'_{(k+1)i}\cup V'_{(k+1)i+1}\cup \dots \cup V'_{(k+1)(i+1)-1})$. Then $V_0,V_1,\dots$ is a partition of V(G). Moreover, if $v\in V_i$ and $w\in V_j$ for some edge vw of G, then $|i-j|\leqslant 1$. Thus $V_1,V_2,\dots$ is a layering of G. Since each layer in G consists of at most $k+1$ layers in $G'$, the layered treewidth of this decomposition is at most $(4g+6)(k+1)$.    $\square$

Theorems 9 and 5 imply:

Theorem 10

Every n-vertex (g, k)-planar graph has treewidth at most

$$2\sqrt{(4g+6)(k+1)n}.$$

We now show that this bound is tight up to a constant factor.

Theorem 11

For all $g,k\geqslant 0$ and infinitely many n there is an n-vertex (g, k)-planar graph with treewidth $\varOmega (\sqrt{(g+1)(k+1)n})$.

The proof of this result depends on the separation properties of the $p\times q\times r$ grid graph (which is $(r-1)$-planar). The next two results are not optimal, but have simple proofs and are all that is needed for the main proof that follows.

Lemma 3

For $q\geqslant (\frac{1}{1-\epsilon })r$, every $\epsilon$-separator of the $q \times r$ grid graph has size at least r.

Proof

Let S be a set of at most $r-1$ vertices in the $q\times r$ grid graph. Some row R avoids S, and at least $q-r+1$ columns avoid S. The union of these columns with R induces a connected subgraph with at least $(q-r+1)r>\epsilon qr$ vertices. Thus S is not an $\epsilon$-separator.    $\square$

Lemma 4

For $p\geqslant q\geqslant (\frac{1}{1-\epsilon })r$, every $\epsilon$-separator of the $p\times q \times r$ grid graph has size at least $(\frac{1-\epsilon }{1+\epsilon })qr$.

Proof

Let G be the $p\times q \times r$ grid graph. Let $n:=|V(G)|=pqr$. Let S be an $\epsilon$-separator of G. Let $A_1,\dots ,A_c$ be the components of $G-S$. Thus $|A_i|\leqslant \epsilon n$. For $x\in [p]$, let $G_x :=\{(x,y,z):y\in [q],z\in [r]\}$ called a slice. Say $G_x$ belongs to $A_i$ and $A_i$ owns $G_x$ if $|A_i\cap G_x| \geqslant \frac{1+\epsilon }{2} qr$. Clearly, no two components own the same slice. First suppose that at least two components each own a slice. That is, $G_v$ belongs to $A_i$ and $G_w$ belongs to $A_j$ for some $v<w$ and $i\ne j$. Let $X:=\{(y,z):(v,y,z)\in G_v,\,(w,y,z)\in G_w\}$. Then $|X|\geqslant 2(\frac{1+\epsilon }{2})qr-qr=\epsilon qr$. For each $(y,z)\in X$, the ‘straight’ path $(v,y,z), (v+1,y,z),\dots ,(w,y,z)$ contains some vertex in S. Since these paths are pairwise disjoint, $|S|\geqslant |X|\geqslant \epsilon qr\geqslant \frac{1-\epsilon }{1+\epsilon }qr$ (since $\epsilon >\frac{1}{2}$). Now assume that at most one component, say $A_1$, owns a slice. Say $A_1$ owns t slices. Thus $t(\frac{1+\epsilon }{2})qr \leqslant |A_i|\leqslant \epsilon pqr$ and $t\leqslant \frac{2\epsilon }{1+\epsilon }p$. Hence, at least $(1-\frac{2\epsilon }{1+\epsilon })p$ slices belong to no component. For such a slice $G_v$, each component of $G_v-S$ is contained in some $A_i$ and thus has at most $(\frac{1+\epsilon }{2})qr$ vertices. That is, $S\cap G_v$ is a $(\frac{1+\epsilon }{2})$-separator of the $q\times r$ grid graph induced by $G_v$. By Lemma 3, $|S\cap G_v|\geqslant r$. Thus $|S|\geqslant (1-\frac{2\epsilon }{1+\epsilon })pr\geqslant (\frac{1-\epsilon }{1+\epsilon })qr$.    $\square$

Proof

(of Theorem 11 ). Let $r:= k+1$.

First suppose that $g\leqslant 19$. Let G be the $q\times q\times r$ grid graph where $q\geqslant 2r$. As observed above, G is k-planar and thus (g, k)-planar. Lemma 4 implies that every $\frac{1}{2}$-separator of G has size at least $\frac{1}{3} qr$. Lemma 1 thus implies that G has treewidth at least $\frac{1}{3} qr-1$, which is at least $\varOmega (\sqrt{(g+1)(k+1)n})$, as desired.

Now assume that $g\geqslant 20$. By Lemma 2 there is a 4-regular expander H on $m:=\lfloor {\frac{g}{4}}\rfloor \geqslant 5$ vertices. Thus H has 2m edges, H embeds in the orientable surface with 2m handles, and thus has Euler genus at most $4m\leqslant g$. We may assume that $q:=\sqrt{n/rm}$ is an integer with $q\geqslant 8r$. Let G be obtained from H by replacing each vertex v of H by a copy of the $q\times q\times r$ grid graph with vertex set $D_v$, and replacing each edge of H by a matching of qr edges, so that $G[D_v\cup D_w]$ is a $2q\times q\times r$ grid, as shown in Fig. 2. Thus G is (g, k)-planar with $q^2rm=n$ vertices.

Fig. 2.

Construction of G in the proof of Theorem 11.

Let S be a $\frac{1}{2}$-separator in G. Let $A_1,\dots ,A_c$ be the components of $G-S$. Thus $|A_i|\leqslant \frac{1}{2}n$ for $i\in [c]$. Initialise sets $S':=A'_1:=\dots :=A'_c:=\emptyset$.

For each vertex v of H, if $|S\cap D_v|\geqslant \frac{qr}{14}$ then put $v\in S'$. Otherwise, $|S\cap D_v| < \frac{qr}{14}$. Note that Lemma 4 is applicable with $\epsilon =\frac{13}{15}$ since $q\geqslant 8r>\frac{1}{1-13/15}r$ and $\frac{1-13/15}{1+13/15}=\frac{1}{14}$. Lemma 4 thus implies that $S\cap D_v$ is not a $\frac{13}{15}$-separator. Hence some component of $D_v-S$ has at least $\frac{13}{15}q^2r$ vertices. Since $\frac{13}{15}>\frac{1}{2}$, exactly one component of $D_v-S$ has at least $\frac{13}{15}q^2r$ vertices. This component is a subset of $A_i$ for some $i\in [c]$; add v to $A'_i$. Thus $S',A'_1.\dots ,A'_c$ is a partition of V(H).

We now prove that $S'$ is a $\frac{15}{26}$-separator in H. Suppose that $v\in A'_i$ and $w\in A'_j$ for some edge vw of H. Let D be the vertex set of the $2q\times q\times r$ grid graph induced by $D_v\cup D_w$. Since $v\not \in S'$ and $w\not \in S'$, we have $|S\cap D_v|<\frac{qr}{14}$ and $|S\cap D_w|<\frac{qr}{14}$. Thus $|S\cap D| <\frac{qr}{7}$. Note that Lemma 4 is applicable with $\epsilon =\frac{3}{4}$ since $q\geqslant 8r>\frac{1}{1-3/4}r$ and $\frac{1-3/4}{1+3/4}=\frac{1}{7}$. Lemma 4 thus implies that $S\cap D$ is not a $\frac{3}{4}$-separator of G[D]. Hence some component X of $G[D]-S$ contains at least $\frac{3}{4}|D|=\frac{3}{2}q^2r$ vertices. Each of $D_v$ and $D_w$ can contain at most $q^2r$ vertices in X. Thus $D_v$ and $D_w$ each contain at least $\frac{1}{2}q^2r$ vertices in X. Thus, by construction, v and w are in the same $A'_i$. That is, there is no edge of H between distinct $A'_i$ and $A'_j$, and each component of $H-S'$ is contained in some $A'_i$. For each $i\in [c]$, we have $\frac{1}{2}q^2rm\geqslant |A_i|\geqslant \frac{13}{15}q^2r|A'_i|$ implying $|A'_i| \leqslant \frac{15}{26}m$. Therefore $S'$ is a $\frac{15}{26}$-separator in H.

By Lemma 2, $|S'|\geqslant \beta m$ for some constant $\beta >0$. Thus $|S|\geqslant \frac{qr}{14}|S'|\geqslant \frac{\beta }{14}mqr$. By Lemma 1, G has treewidth at least $\frac{\beta }{14}mqr-1=\frac{\beta }{14}\sqrt{mrn}-1\geqslant \varOmega (\sqrt{g(k+1)n})$, as desired.    $\square$

Note that the proof of Theorem 11 in the case $k=0$ is very similar to that of Gilbert, Hutchison, and Tarjan [6].

For $gk\geqslant n$ the trivial upper bound of ${{\mathrm{tw}}}(G)\leqslant n$ is better than that given in Theorem 10. We conclude that the maximum treewidth of (g, k)-planar n-vertex graphs is $\varTheta (\min \{n,\sqrt{(g+1)(k+1)n}\})$ for arbitrary g, k, n. This completes the proof of Theorem 2.

5 Drawings with Few Crossings per Edge

This section studies the following natural conjecture: for every surface $\Sigma$ of Euler genus g, every graph G with m edges has a drawing in $\Sigma$ with $O(\frac{m}{g+1})$ crossings per edge. This conjecture is trivial at both extremes: with $g=0$, every graph has a straight-line drawing in the plane (and therefore a drawing in the sphere) with at most m crossings per edge, and with $g=2m$, every graph has a drawing in the orientable surface with one handle per edge. Moreover, if this conjecture is true, it would provide a simple proof of Theorem 11 in the same manner as the proof of Theorem 8.

Our starting point is the following well-known result of Leighton and Rao [14, Theorem 22, p. 822]:

Theorem 12

(Leighton and Rao [14]). Let G be a graph with bounded degree and n vertices, mapped one-to-one onto the vertices of an expander graph H. Then the edges of G can be mapped onto paths in H so that each path has length $O(\log n)$ and each edge of H is used by $O(\log n)$ paths.

It is straightforward to extend this result to regular graphs G of unbounded degree, with the number of paths per edge of H increasing in proportion to the degree. However, there are two difficulties with using it in our application. First, it does not directly handle graphs in which there is considerable variation in degree from vertex to vertex: in such cases we would want the number of paths per edge to be controlled by the average degree in G, but instead it is controlled by the maximum degree. And second, it does not allow us to control separately the sizes of G and H; instead, both must have the same number of vertices. To handle these issues, we do not map the vertices of our input graph G directly to the vertices of an expander H; instead, we keep the vertices of G and the vertices of H disjoint from each other, connecting them by a bipartite graph that balances the degrees, according to the following lemma.

Lemma 5

Let $d_1,d_2,\dots ,d_n$ be a sequence of positive integers, and let q be any positive integer. Then there exists a bipartite graph with colour classes $\{v_1,\dots ,v_n\}$ and $\{w_1,\dots ,w_q\}$, at most $n+q-1$ edges, and a labelling of the edges with positive integers, such that

• each vertex $v_i$ is incident to a set of edges whose labels sum to $d_i$, and

• each pair of distinct vertices $w_i$ and $w_j$ are incident to sets of edges whose label sums differ by at most 1.

Proof

Preassign label sums of $\lfloor \sum d_i/q \rfloor$ or $\lceil \sum d_i/q \rceil$ to each vertex $w_i$ so that the resulting values sum to $\sum d_i$. We will construct a bipartite graph and a labelling whose sums match the numbers $d_1,\dots ,d_n$ on one side of the bipartition and whose sums match the preassigned numbers on the other side.

Build this graph and its labelling one edge at a time, starting from a graph with no edges. At each step, let $v_i$ and $w_j$ be the vertices on each side of the bipartition with the smallest indices whose edge labels do not yet sum to the required values, add an edge from $v_i$ to $w_j$, and label this edge with the largest integer that does not exceed the required sum on either vertex.

Each step completes the sum for at least one vertex. Because the required values on the two sides of the bipartition both sum to $\sum d_i$, the final step completes the sum for two vertices, $v_n$ and $w_q$. Therefore, the total number of steps, and the total number of edges added to the graph, is at most $n+q-1$.    $\square$

Fig. 3.

A graph (left) with degree sequence 7, 5, 5, 4, 3, 3, 2, 1 and a bipartite graph (right) formed from this degree sequence by Lemma 5. The large numbers are the edge labels of the lemma, and the small numbers along the top and bottom of the bipartite graph give the sums of incident edge labels at each vertex. The top sums match the given degree sequence, while the bottom sums all differ by at most 1.

By combining this load-balancing step with the Leighton-Rao expander-routing scheme, we may obtain a more versatile mapping of our given graph G to a host graph H, with better control over the genus of the surface we obtain from H. This genus will be determined by the cyclomatic number of H, where the cyclomatic number of a graph with n vertices and m edges is $m-n+1$. This number is the dimension of the cycle space of the graph, and the first Betti number of the topological space obtained from the graph by replacing each edge by a line segment.

Lemma 6

Let G be an arbitrary graph, with m edges, and let Q be a q-vertex bounded-degree expander graph. Then there exists a host graph H, a one-to-one mapping of the vertices of G to a subset of vertices of H, and a mapping of the edges of G to paths in H, with the following properties:

• The vertices of H that are not images of vertices in G induce a subgraph isomorphic to Q.

• The image of an edge e in G forms a path of length $O(\log q)$ that starts and ends at the image of the endpoints of e, and passes through the image of no other vertex of G.

• Each vertex of H that is not an image of a vertex in G is crossed by $O((m\log q)/q)$ paths.

• The cyclomatic number of H is O(q).

Proof

Let the vertices of G be $u_1,\dots ,u_n$. Apply Lemma 5 to the degree sequence of G to form a bipartite graph H with bipartition $\{v_1,\dots ,v_n\},\{w_1,\dots ,w_q\}$ (Fig. 3). Then add edges between pairs of vertices $(w_i,w_j)$ so that $\{w_1,\dots ,w_q\}$ induces a subgraph isomorphic to Q. In this way, each vertex $u_i$ in G is mapped to a vertex $v_i$ in H so that the mapping is one-to-one and the unmapped vertices form a copy of Q, as required. The cyclomatic number of H equals the cyclomatic number of Q, plus $n+q-1$ (for the added edges in the bipartite graph), minus n (for the added vertices relative to Q). These two added and subtracted terms cancel, leaving the cyclomatic number of Q plus $q-1$, which is O(q) as required.

It remains to find paths in H corresponding to the edges in G. Assign each edge $u_iu_j$ of G to a pair of vertices $(w_{i'},w_{j'})$ adjacent to the images $v_i$ and $v_j$ in H, so that the number of edges of G assigned to each edge between $\{v_1,\dots ,v_n\}$ and $\{w_1,\dots ,w_q\}$ equals the corresponding label. Complete each path by applying Theorem 12 to the copy of Q; this gives paths of length $O(\log q)$ connecting each pair $(w_{i'},w_{j'})$ obtained in this way. These pairs do not form a bounded-degree graph, but they can be partitioned into O(m / q) bounded-degree graphs, each of which causes each vertex in the copy of Q to be crossed $O(\log q)$ times. Combining these suproblems, each vertex in the copy of Q is crossed by a total of $O((m\log q)/q)$ paths, as required.    $\square$

We are now ready to prove the existence of embeddings with small local crossing number, on surfaces of arbitrary genus.

Proof

(of Theorem 3 ). Given a graph G, to be embedded on a surface with at most g handles and with few crossings per edge, choose q so that the O(q) bound on the cyclomatic number of the graph H in Lemma 6 is at most g, and apply Lemma 6 to find a graph H and a mapping from G to H obeying the conditions of the lemma.

To turn this mapping into the desired embedding of G, replace each vertex of degree d in H by a sphere, punctured by the removal of d unit-radius disks, and form a surface (as a cell complex, not necessarily embedded into three-dimensional space) by replacing each edge xy of H by a unit-radius cylinder connecting boundaries of removed disks on the spheres for vertices x and y. The number of handles on the resulting surface (shown in Fig. 4) equals the cyclomatic number of H, which is at most g.

Fig. 4.

A topological surface obtained by replacing each vertex of a graph by a punctured sphere, and each edge of the graph by a cylinder connecting two punctures. Image Square_pyramid_pyramid.png by Tom Ruen on Wikimedia commons, made available under a Creative Commons CC-BY-SA 4.0 International license.

Embed each vertex of G as an arbitrarily chosen point on the sphere of the corresponding vertex of H, and each edge of G as a curve through the sequence of spheres and cylinders corresponding to its path in H. Choose this embedding so that no intersection of edge curves occurs within any of the cylinders, and so that every pair of edges that are mapped to curves on the same sphere meet at most once, either at a crossing point or a shared endpoint.

Because the spheres that contain vertices of G only contain curves incident to those vertices, they do not have any crossings. Each edge is mapped to a curve through $O(\log g)$ of the remaining spheres, and can cross at most $O((m\log g)/g)$ other curves within each such sphere. Therefore, the maximum number of crossings per edge is $O((m\log ^2 g)/g)$.    $\square$