Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 157–162
The genus crossing number
Bojan Mohar ∗
Department of Mathematics, Simon Fraser University
Burnaby, B.C. V5A 1S6, Canada
Received 1 August 2007, accepted 11 July 2009, published online 26 September 2009
Abstract
Pach and Tóth [5] introduced a new version of the crossing number parameter, called
the degenerate crossing number, by considering proper drawings of a graph in the plane
and counting multiple crossing of edges through the same point as a single crossing when
all pairwise crossings of edges at that point are transversal. We propose a related parame-
ter, called the genus crossing number, where edges in the drawing need not be represented
by simple arcs. This relaxation has two important advantages. First, the genus crossing
number is invariant under taking subdivisions of edges and is also a minor-monotone graph
invariant. Secondly, it is “computable” in many instances, which is a rare phenomenon in
the theory of crossing numbers. These facts follow from the proof that the genus cross-
ing number is indeed equal to the non-orientable genus of the graph. It remains an open
question if the genus crossing number can be strictly smaller than the degenerate crossing
number of Pach and Tóth. A relation to the minor crossing number introduced by Bokal,
Fijavž, and Mohar [1] is also discussed.
Keywords: Crossing number, genus.
Math. Subj. Class.: 05C10
1 Introduction
Let G be a graph. The crossing number of G, denoted by CR(G), is the minimum number
of edge-crossings taken over all proper drawings of G in the plane. By a drawing we refer
to a representation of the graph in the Euclidean plane, where vertices are points in the
plane and edges are piecewise linear arcs joining their end-vertices. A drawing is proper
if edges are simple arcs and their interiors do not contain vertices of the graph. If k edges
intersect at the same point (not a vertex), then each of the
(
k
2
)
pairwise crossings counts
∗Supported in part by the ARRS, Research Program P1–0507, and by an NSERC Discovery Grant. On leave
from Department of Mathematics, FMF & IMFM, University of Ljubljana, 1000 Ljubljana, Slovenia.
E-mail address: mohar@sfu.ca (Bojan Mohar)
Copyright c© 2009 DMFA Slovenije
158 Ars Math. Contemp. 2 (2009) 157–162
towards the computation of the total number of crossings of the drawing when we consider
CR(G).
Pach and Tóth [5] introduced a modified definition of the crossing number of a graphG,
called the degenerate crossing number and denoted by CR(G), where a multiple crossing at
a point p in the plane is counted as a single crossing if all pairs of edges passing through p
intersect transversally, i.e., they locally intersect at p and the intersection is not tangential.
Such a point pwill be referred to as a crossing point. The initial goal to introduce this notion
was to investigate to what extent does this modification affect the value of the crossing
number.
Pach and Tóth [5] also introduced the notion of a crossing number, denoted by CR∗(G),
where multiple, pairwise transversal crossing at the same point is counted as a single
crossing, but two distinct edges are allowed to cross each other at most once. While
CR∗(G) ≥ CR(G) holds for any graph G, it is proved in [5] that CR∗(G) can be much
bigger than CR(G), thus showing that multiple crossings between distinct edges may help
reducing the corresponding value of the crossing number.
The purpose of this paper is to propose another modification, where we do not insist
that edges are simple arcs. We allow self-crossings of arcs representing the edges, but all
self-crossings should be transversal. For reasons that will become apparent soon, we call
the minimum number of crossing points of such drawings of G the genus crossing number
of G and denote it by GCR(G). It is clear that
GCR(G) ≤ CR(G) ≤ CR∗(G) ≤ CR(G). (1.1)
It is an open question if GCR(G) can be strictly smaller than CR(G). We shall discuss this
issue in Section 3. Other inequalities in (1.1) can be strict inequalities, see [5].
The newly introduced version of the crossing number has some advantages over other
notions of the crossing number mentioned above or treated elsewhere in the literature, see,
e.g. [4, 6]:
(1) The genus crossing number is the first crossing number invariant, for which exact
values can be determined for important families of graphs, like the complete or com-
plete multipartite graphs, the hypercubes, etc. See Section 2 for details. Despite this
fact, it is still NP-hard to compute the genus crossing number for arbitrary graphs.
(2) The genus crossing number is minor-monotone, i.e., if a graph H is a minor of G,
then GCR(H) ≤ GCR(G).
(3) Unlike CR and CR∗, the genus crossing number is a topological invariant, i.e., it
does not change if we subdivide edges. Moreover, if we subdivide each edge of G
by inserting sufficiently many vertices of degree 2, then we can get rid of all multiple
crossings and all self-crossings of edges with respect to some optimal drawing of G.
Consequently, the resulting subdivision S satisfies
CR∗(G) ≥ CR(G) ≥ CR∗(S) = CR(S) = GCR(S) = GCR(G).
2 The genus crossing number
As stated in the introduction, we shall consider the version of the crossing number where
edges need not be simple Jordan curves. They are allowed to self-intersect and also two dis-
tinct edges are allowed to intersect more than once. However, interiors of edges should not
B. Mohar: The genus crossing number 159
contain vertices of the graph and all intersections should be transversal, i.e., non-tangential.
In particular, if edges cross at a point p, possibly some edges passing through p more than
once, we require that all passes through p are transversal to each other. Now we define
GCR(G) as the minimum integer k such that G has a drawing in the plane with the above
properties and with k points where distinct edges cross each other.
Recall that the nonorientable genus g̃(G) of a graph G is the minimum genus of a non-
orientable surface in whichG can be embedded, cf. [3]. Having a drawing ofG in the plane
with g = GCR(G) points at which the edges cross, each such crossing can be replaced by a
crosscap, yielding an embedding ofG into the non-orientable surface of genus g (if g > 0).
This shows that GCR(G) ≥ g̃(G) if G is nonplanar. It is interesting that the converse also
holds:
Theorem 2.1. Let G be a non-planar graph. Then GCR(G) = g̃(G).
Proof. Let g = g̃(G), and let us consider an embedding of G in the non-orientable surface
S of genus g. Since S is homeomorphic to the connected sum of g projective planes, it
contains g pairwise disjoint 1-sided simple closed curves α1, . . . , αg . We may assume that
none of these curves passes through a vertex of G and that each of them intersects G in
finitely many points. By cutting the surface along all curves α1, . . . , αg , we obtain the
surface homeomorphic to the sphere with g holes. By contracting each of these holes to a
point, a drawing of G in the plane is obtained. It is easy to see that each contracted hole
gives rise to a (multiple) crossing, in which all edges cross transversally. This shows that
GCR(G) ≤ g = g̃(G).
Known results about the nonorientable genus of graphs (see, e.g., [2, 3, 8]) yield exact
values for all most common families of graphs, in particular for the complete and complete
bipartite graphs:
Corollary 2.2. For n ≥ 8 and for k ≥ l ≥ 3, we have:
GCR(Kn) =
⌈
(n− 3)(n− 4)
6
⌉
and GCR(Kk,l) =
⌈
(k − 2)(l − 2)
2
⌉
.
We refer to monographs on topological graph theory [2, 3, 8] for many other exact
results about the non-orientable genus, and hence also for the genus crossing number of
graphs. Theorem 2.1 thus enables us to compute or estimate the genus crossing number for
most important families of graphs, like the complete or complete multipartite graphs, the
hypercubes, etc. In that sense, GCR is the first crossing number invariant, for which exact
values can be determined for so many graphs.
Nevertheless, it is still hard to compute the genus crossing number for arbitrary graphs.
This follows from Thomassen’s results in [7], where it is shown that it is NP-hard to com-
pute the non-orientable genus.
Corollary 2.3. It is NP-hard to determine the genus crossing number.
There are other consequences of Theorem 2.1. For instance, it is clear that GCR is
a minor-monotone graph parameter. This issue is treated in more details in Section 4.
Another easy consequence are upper and lower bounds on GCR(G).
160 Ars Math. Contemp. 2 (2009) 157–162
Theorem 2.4. Let G be a connected graph of order n ≥ 2 and with e edges, and let g be
the girth of G. Let r be the maximum number of edges in an outerplanar subgraph of G.
Then
g − 2
g
e− n+ 2 ≤ GCR(G) ≤
{
e− r − 1 if r < e,
0 if r = e.
Proof. If G is not simple, then g ≤ 2, and the lower bound is trivial. Since adding loops
and parallel edges has no effect on GCR(G) and does not decrease the value of e − r − 1,
we may henceforth assume that G is a simple graph. Let c = GCR(G), and let us consider
an embedding of G in Nc. Let f be the number of facial walks. The girth condition shows
that f ≤ 2e/g. Now, Euler’s formula implies that c ≥ 2−n+ e−f ≥ 2−n+ (g−2)e/g.
This yields the lower bound.
To prove the upper bound, let H be a maximal outerplanar graph of G. Consider an
embedding of H in the plane so that all vertices of G are on the boundary of the outer
face. Clearly, H is a spanning subgraph of G. Now let us define an embedding of G as
follows. (Cf. [3] for details about combinatorial description of 2-cell embeddings using
rotation systems and signatures.) First, define an arbitrary rotation system for G so that all
bounded faces of H remain facial walks with respect to the extended embedding. Finally,
if |E(G) \ E(H)| = e − r > 0, set the signature on one edge e0 ∈ E(G) \ E(H) to
be positive, and set it negative for all other edges in E(G) \ E(H). By extending the
embedding of H edge-by-edge, e0 being the last one to be added, we see that in all partial
embeddings obtained during this process, the outer face of H is replaced by a single facial
walk. This means that each added edge decreases the Euler characteristic of the resulting
surface by 1. On the other hand, the last edge e0 divides the outer facial walk into two,
and hence does not change the Euler characteristic. Thus, the nonorientable genus of the
resulting surface (if e− r ≥ 2) is equal to e− r− 1. If e− r ≤ 1, then clearly, G is planar,
so this completes the proof of the upper bound.
Let us observe that r ≥ n− 1 since every spanning tree is outerplanar, and that r ≥ n
if G is not a tree.
Theorem 2.4 is a slight improvement over the bounds derived in [5] for the degenerate
crossing number. The lower bound is the same as the one in [5] but is given for GCR(G)
instead for CR(G). The upper bound improves the bound CR(G) ≤ e proved in [5].
3 Degenerate and genus crossing number
As we have observed earlier, the genus crossing number is always a lower bound for the
degenerate crossing number. However, it is an open question if these two notions define
different graph invariants. In fact, after several unsuccessful attempts to construct examples
showing that the genus and the degenerate crossing number are distinct, we are inclined to
propose the following
Conjecture 3.1. For every graph G, we have GCR(G) = CR(G).
Let us outline some thoughts related to this problem. Recall that the genus crossing
number is related to the notion of having the graph embedded in a non-orientable surface
Ng of genus g and having a collection of g pairwise disjoint 1-sided simple closed curves in
Ng which yield an embedding in a planar surface (homeomorphic to the sphere with g discs
cut out) when the surface is cut along them. Such a collection of curves will be called a
B. Mohar: The genus crossing number 161
planarizing system of disjoint 1-sided curves, shortly a PD1S-system in Ng . The following
result is a simple consequence of the definitions.
Lemma 3.2. Let G be a graph and g be a positive integer. Then CR(G) ≤ g if and only if
G has an embedding in the non-orientable surface Ng of genus g and there exists a PD1S-
system Γ of curves in Ng such that every curve in Γ intersects each edge of G at most
once.
This lemma may be of use when trying to settle Conjecture 3.1. Our next result shows
that in order to prove Conjecture 3.1, it suffices to verify it for triangulations of non-
orientable surfaces.
Proposition 3.3. Conjecture 3.1 is equivalent to the statement that for every positive integer
g, every triangulationG of the non-orientable surface Ng admits a PD1S-system Γ of curves
in Ng such that every curve in Γ intersects each edge of G at most once.
Proof. Clearly, if a triangulation G would not satisfy the stated property, it would be a
counterexample to Conjecture 3.1.
Conversely, let H be a counterexample to the conjecture and let g = g̃(H) < CR(H).
Embed H in Ng and and extend it to a triangulation G of Ng (by adding edges and, if
necessary, new vertices). Then GCR(G) = g̃(G) = g and CR(G) ≥ CR(H) > g.
It may be that a stronger conjecture holds. Recall that a pseudotriangulation of a surface
S is a multigraph (where we allow loops and multiple edges), which is 2-cell embedded in
S such that each facial walk has length three.
Conjecture 3.4. For every positive integer g, every loopless pseudotriangulation G of Ng
admits a PD1S-system Γ of curves in Ng such that every curve in Γ intersects each edge of
G at most once.
We do not even know of examples of pseudotriangulations with loops, where the only
requirement is that loops are surface non-separating, for which Conjecture 3.4 would not
hold. However, if we allow surface separating loops, counterexamples are easy to find.
4 Minor and genus crossing number
Bokal, Fijavž, and Mohar [1] introduced the notion of a crossing number, called the minor
crossing number and denoted by MCR(G), which is minor-monotone: if a graph H is a
minor of a graph G, then MCR(H) ≤ MCR(G). This is achieved by defining the minor
crossing number in the following way:
MCR(G) = min{CR(H) | G is a minor of H}.
Theorem 2.1 implies that the genus crossing number is also minor-monotone.
Proposition 4.1. If a graph H is a minor of a graph G, then GCR(H) ≤ GCR(G).
After having noted this relationship between the minor and the genus crossing number,
it may be of interest to see to what extent are they related.
Proposition 4.2. For every graph G we have GCR(G) ≤ MCR(G).
162 Ars Math. Contemp. 2 (2009) 157–162
Proof. LetH be a graph such thatG is a minor ofH and CR(H) = MCR(G). By replacing
each crossing in an optimal drawing of H by a crosscap, we see that g̃(H) ≤ CR(H).
Since G is a minor of H , we have g̃(G) ≤ g̃(H). Combining all these inequalities, we see
that
GCR(G) = g̃(G) ≤ g̃(H) ≤ CR(H) ≤ MCR(G),
which we were to prove.
It can happen that the minor crossing number is much bigger than the genus crossing
number. For example, it is proved in [1] that MCR(Kn) ≥ d 14 (n−3)(n−4)e. On the other
hand, Corollary 2.2 shows that GCR(Kn) = d 16 (n − 3)(n − 4)e. These results imply not
only that MCR and GCR are distinct, but also that these crossing number parameters may
be much different even for very sparse graphs. The following result gives further examples
and some additional information.
Theorem 4.3. For every positive integer n there is a graphG of order n such that MCR(G)−
GCR(G) ≥ Ω(n2). Moreover, if n is even, there exists a cubic graph H of order n such
that CR(H) = MCR(H) ≥ GCR(H) + Ω(n).
Proof. The first claim holds for G = Kn as argued above. To prove the second claim,
we shall assume that n is of the form n = m(m − 3), where m is a positive integer. The
general case follows easily from this one, and the details are left to the reader.
Let us consider an embedding of the complete graphKm into the nonorientable surface
of genus g = d 16 (m− 3)(m− 4)e. By expanding each vertex into a tree on m− 3 vertices,
we can obtain a cubic graph H embedded in the same surface such that Km is a minor of
H . This shows that the nonorientable genus ofH is equal to g. SinceH has n = m(m−3)
vertices, we conclude that GCR(H) = g = 16 n+O(n
1/2).
On the other hand, MCR(H) = CR(H) ≥ MCR(Km) ≥ 14 n−O(n
1/2). Both inequal-
ities show that MCR(H)− GCR(H) ≥ 112 n−O(n
1/2).
References
[1] D. Bokal, G. Fijavž and B. Mohar, The minor crossing number, SIAM J. Discrete Math. 20
(2006), 344–356.
[2] J. L. Gross, T. W. Tucker, Topological Graph Theory, Wiley – Interscience, New York, 1987.
[3] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore,
2001.
[4] J. Pach and G. Tóth, Which crossing number is it anyway? J. Combin. Theory Ser. B 80 (2000),
225–246.
[5] J. Pach and G. Tóth, Degenerate crossing numbers, Discrete Comput. Geom. 41 (2009), 376–
384.
[6] L. Székely, A successful concept for measuring non-planarity of graphs: the crossing number,
Discrete Math. 276 (2004), 331–352.
[7] C. Thomassen, The graph genus problem is NP-complete, J. Algorithms 10 (1989), 568–576.
[8] A. T. White, Graphs, Groups and Surfaces, North-Holland, 1973; Revised Edition: North-
Holland, 1984.