Crossing number, pair-crossing number, and expansion.
The <i>crossing number</i> cr(<i>G</i>) of a graph <i>G</i> is the minimum possible number of edge crossings in a drawing of <i>G</i> in the plane, while the <i>pair-crossing number</i> pcr(<i>G</i>) is the smallest number of pairs of edges that cross in a drawing of <i>G</i> in the plane. While cr(<i>G</i>)  pcr(<i>G</i>) holds trivially, it is not known whether a strict inequality can ever occur (this question was raised by Mohar and Pach and Tth). We aim at bounding cr(<i>G</i>) in terms of pcr(<i>G</i>). Using the methods of Leighton and Rao, Bhatt and Leighton, and Even, Guha and Schieber, we prove that One of the main steps is an analogy of the well-known lower bound cr(<i>G</i>) = (<i>b</i>(<i>G</i>)<sup>2</sup>) - <i>O</i>(ssqd(<i>G</i>)), where <i>b(G)</i> is the <i>bisection width</i> of <i>G</i>, that is, the smallest number of edges that have to be removed so that no component of the resulting graph has more than 2/3 <i>n</i> vertices. We show that We also prove by similar methods that a graph <i>G</i> with crossing number log<sup>2</sup> <i>n</i> has a nonplanar subgraph on at most <i>O</i>(<i>nm</i> log<sup>2</sup> <i>n</i>/<i>k</i>) vertices, where <i>m</i> is the number of edges,  is the maximum degree in <i>G</i>, and <i>C</i> is a suitable sufficiently large constant.
Introduction
By a drawing of a (multi)graph G, we mean a drawing in the plane such that every edge
is represented by an arc. The arcs are allowed to cross, but they may not pass through
vertices (except for their endpoints) and no point is an internal point of three or more arcs.
A crossing is a common internal point of two arcs.
The crossing number cr(G) is the minimum possible number of crossings in a drawing of
G. The pair-crossing number pcr(G) is the minimum possible number of (unordered) pairs of
edges that cross in a drawing of G. Pach and Toth [13] were the rst to formulate explicitly
the denition of pcr(G), and they raised the problem of whether
which had previously been overlooked in papers on the crossing number of graphs.
Surprisingly, this problem appears quite challenging. A natural approach to proving
equality is, given a drawing witnessing pcr(G), to modify it locally so that multiple crossings
of pairs of edges are eliminated. An example of Kratochvl and Matousek [5] shows that
in general, given a drawing, it need not be possible to eliminate multiple crossings of pairs
without introducing new crossing pairs. Namely, there is a graph G on n vertices and a
Supported by the Ministry of Education of the Czech Republic as project LN00A056.
drawing D 0 of G such that if D is any drawing of G for which every pair of crossing edges
also crosses in D 0 , then some two edges cross at least 2
n) times in D. In this example, the
drawing D 0 is not one minimizing the pair-crossing number, so it might be still possible to
modify an optimal drawing locally, but at least this does not appear straightforward.
In view of these di-culties, it is natural to seek upper bounds on cr(G) as a function
of pcr(G) (and possibly of other parameters of G). Pach and Toth [13] proved a quadratic
They actually prove a stronger result, involving the odd crossing
number (the minimum number of pairs of edges in a drawing that cross an odd number
of times), and their proof is rather involved. Valtr [18] recently improved this bound to
log for every graph with with a simple proof. The crossing
number and pair-crossing number for random graphs was studied by Pach, Spencer, and
Toth [11].
In the rst part of this paper, we combine known techniques for bounding the crossing
number of graphs, due to Leighton and Rao [8] and Bhatt and Leighton [2] (with a recent
improvement by Even et al. [3]), with some additional observations, and we prove an upper
bound on cr(G) in terms of pcr(G), which is interesting for graphs with pcr(G) large compared
to
. The last quantity will appear many times in our considerations, and
so we introduce the notation ssqd(G) for it. The letter n will denote the number of vertices
of G throughout this paper.
Theorem 1 For every graph G we have
log 3
In particular, if G has maximum degree bounded by a constant and pair-crossing number at
least n, then
The main step in the proof is a nontrivial lower bound on the pair-crossing number.
Several methods are known for bounding below the crossing number of a given graph; see
Shahrokhi et al. [16] for a survey. The well-known lower bound in terms of the number of
edges,

(1)
for all G with n vertices and m  4n edges, proved by Ajtai, Chvatal, Newborn, and
Szemeredi [1] and independently by Leighton [7], is also valid for the pair-crossing number,
as is easily checked.
Another important lower bound is
where b(G) denotes the bisection width of G, that is, the smallest number of edges between
(G)j. This bound was
proved by Leighton [6] for graphs of bounded degree and by Pach, Shahrokhi, and Szegedy
[10], and independently by Sykora and Vrt'o [17], for general graphs. The usual proof fails
miserably if one tries to replace the crossing number by the pair-crossing number: In the
rst step of the proof, one considers a drawing with the minimum crossing number and
replaces every crossing by a new vertex of degree 4, obtaining a planar graph and applying
a separator theorem. For the pair-crossing number, we have almost no control over the total
number of crossings (and thus the size of the resulting planar graph). However, the following
weaker substitute of the lower bound (2) can be proved for the pair-crossing number using a
low-congestion path embeddings [7, 8]:
Theorem 2 For every graph G, we have

log
This almost solves (up to the log 2 n factor) Problem 11 of Pach and Toth [12].
A related problem is to nd an optimal drawing of G in the plane, with respect to cr(G)
or pcr(G). The best known algorithm is by Even et al. [3] and it approximates cr(G)+n (not
just cr(G)!) within a multiplicative factor of O(log 3 n). The procedure is to recursively draw
G on a circle arc, that is, to put vertices on the arc and to draw all edges as straight line
segments. Their bound is an improvement of an earlier result by Bhatt and Leighton [2]. A
corollary of the analysis is that for any graph G, there exists a drawing of G on the circle arc
with at most O(log crossings. Although we are not concerned about drawing
algorithms, the outlined procedure will be used in our proofs.
In Section 5 we investigate \locality" of the crossing number. That is, if cr(G) is large,
must G necessarily have small nonplanar subgraphs? By a detour via edge expansion, in analogy
to the preceding section, we prove the following upper bound on the size of a nonplanar
Theorem 3 Let G be a graph with crossing number cr(G) > C
is the number of edges in G and C is a su-ciently large absolute constant. Then G has a
nonplanar subgraph on at most
O

mn log 2 n
vertices, where  is the maximum degree in G.
In particular, if the maximum degree  is bounded by a constant, the assumption becomes
and the bound for the size of the nonplanar subgraph becomes
O((n log n) 2 =cr(G)).
For graphs with maximum degree bounded by a constant and with
result is nearly optimal, up to a factor of log n. Namely, a constant-degree expander of girth
779 n) (i.e., with minimal length of a cycle
cle n)) has crossing number
all subgraphs on fewer than g vertices are planar (even trees).
Preliminaries
An (edge) cut e(V of a graph G is the set of edges connecting V 1 and V 2 , for
;. The pair called a partition of G, and its size is the number of
edges in the cut e(V
The bisection width b(G) was introduced in the previous section, as the size of a minimal
partition (G)j. (Note that we do not insist on partitioning the
vertices into two parts of equal size; we consider an approximate bisection.) The hereditary
bisection width hb(G) is the maximum of b(H) over all subgraphs H of G. The edge expansion
of G is
An embedding of a graph H in a graph G maps vertices of H to vertices of G and edges
of H to paths in G. More formally, an embedding is a pair (f; '), where
is an injective mapping, and ' is a mapping that assigns to each edge
a path '(e) in G connecting the vertices f(u) and f(v). The congestion of the embedding
is the maximum number of paths in the embedding passing through an edge of G, and the
dilation is the maximum length of a path '(e), e 2 E(H).
The following theorem is one of our main tools; it will be used in the proof of both
Theorem 1 (relating the crossing number and the pair-crossing number; the bound on the
dilation is not needed here) and Theorem 3.
Theorem 4 Let G be a graph on n vertices with edge expansion  and maximum degree .
Then there exists an embedding of the complete graph K n in G with congestion O( 1 n log n)
and dilation O( 1 log n).
As a tool for proving this theorem, we will use concurrent multicommodity
ows, namely
a uniform multicommodity
ow: there is a commodity with demand one for each (unordered)
pair of vertices. A feasible solution of such a multicommodity
ow problem is a system of
ows in G, one
ow for every pair of vertices, with the total
ow through each edge at most
one. The
ow of the feasible solution is the maximum f such that at least f units are
transfered for each commodity. The objective is to nd a feasible solution with a maximal
ow, called the max-
ow of the problem.
The min-cut of the uniform multicommodity
ow problem is
Observe that ' depends only on the graph G and that it is closely related to the expansion
of the graph:n
Proof of Theorem 4. Leighton and Rao [8, Theorem 18] proved that on any graph G there
exists a solution of the uniform multicommodity
ow problem with
ow of
size
'= log n), for
which every
ow path has length at most O( 1 log n), where  is the maximum degree of
G. (Later, Kolman and Scheideler proved an analogous result for a general multicommodity
ow.)
We consider this solution, and we individually rescale each
ow so that one unit
ows
between every pair of vertices. The largest scaling factor is O(' 1 log n), and so the total
ow through each edge after the rescaling is O(' 1 log n) = O( 1 n log n) (using the relation
(3) between ' and ).
The
ow between every pair of vertices is at least one, all
ow paths have the desired
length, and also the maximal
ow through an edge is as desired. It remains to turn each
of the unit-capacity
ows into a path (that is, to make the
ows integral). Observing that
log n, this can be accomplished by the randomized rounding of Raghavan and
Thompson [14, Theorem 3.1], which increases the maximal
ow through an edge only by
another constant factor. 2
In the proof of Theorem 4 we rst produced unit-capacity
ows, and then we turned them
into paths by randomized rounding. Let us remark that this rounding step is not essential
for the forthcoming proofs. The integrality of the
ows only simplies some later arguments
but it is not crucial for them.
Remark. For some classes of graphs, the bounds in Theorem 4 can be improved. A useful
parameter, which to some extent measures the possibility of such an improvement, is the
ow number I 0 denote the instance of the concurrent multicommodity
ow problem in which there is a commodity with demand deg(u)  deg(v)=2jE(G)j for each
pair of vertices (u; v). For a feasible solution S, let D(S) be the length of the longest
ow
path in S and let C(S) be the inverse of the
ow (i.e., the maximum over all commodities
of
ow divided by demand) of S. Then F (G) is the minimum of maxfD(S); C(S)g over all
feasible solutions S of I 0 . The congestion bound in Theorem 4 can be replaced by O(nF ) and
the dilation bound by O(F ) (cf. [4]). We always have log n), where  is the
maximum degree of G, but sometimes F can be smaller by a factor  or log n. For example,
for the hypercube on vertices we have n), and for the 2-dimensional
n mesh we have
n).
3 Pair-crossing number and bisection width: Proof of TheoremWe begin with a simple lemma showing that a graph with large bisection width contains a
large subgraph with large expansion.
Lemma 5 Every graph on n vertices with bisection width b contains a subgraph on at least3 n vertices with edge expansion at least b=n.
Proof. If (G)  b
n , we are done, and otherwise, there is a subset A 1 , 1  jA 1 j  n, that
can be cut by removing at most jA 1 j b
edges. Moreover, jA 1 j < n, for otherwise, we would
get a contradiction to We look at the subgraph induced by V n A 1 ; if it has edge
expansion at least b
n , we can nish, and otherwise, we can cut o a subset A 2 , etc.
At each step, we cut o at most half of the current number of vertices, and so if we do
not nish earlier, we must reach a situation when the current graph, induced by V n
vertices. The set A 1 [    [A k can be separated from
this subgraph by removing at most (jA
edges. This contradiction shows
that we obtain the desired subgraph in some of the earlier steps. 2
To prove Theorem 2, it su-ces, by the lemma just proved, to show that

log
Proof of Theorem 2. By Theorem 4, there exists a set of paths P such that
for each pair fu; vg 2 V
there is a path p uv 2 P connecting u and v, and
for each edge e 2 E, there are at most O( 1 n log n) paths of P going through it.
Let us x a drawing of G witnessing pcr(G). Using the paths from P, we draw the complete
graph K V on the vertex set V : The edge fu; vg of K V is drawn along the path p uv .
Crossings in this drawing of K V come from crossings in the drawing of G and from
crossings near vertices of G. The number of crossing pairs in the drawing of K V induced by a
crossing of edges of G is at most O( 2 n 2 log 2 n), and the number of crossing pairs
caused by crossings of the paths from P near a vertex w is at most O(deg 2 (w) 2 n 2 log 2 n).
Thus,

example by (1), the proof of (4), and thus also of the theorem,
is completed. 2
As was noted after the proof of Theorem 4, the rounding of the (non-integral) multi-
commodity
ow to an integral one (i.e., a system of paths) can easily be avoided. Given
arbitrary unit
ows as in Theorem 4, we can again draw K V using the optimal drawing of
G. In this case, the edge fu; vg of K V is drawn along a path that is chosen at random from
all paths that constitute the
ow between u and v in the solution, with the random choice
made according to the sizes of
ows along these paths. Then we can estimate the expected
pair-crossing number of the resulting drawing of K V and compare it with the pair crossing
number of K V .
4 Drawing by recursive bisection: Proof of Theorem 1
We start with a proof of a slightly weaker version of Theorem 1:
log
We follow the procedure of Bhatt and Leighton [2] for drawing G, in a slightly simplied
form similar to the version in Shahrokhi et al. [15]. The procedure is recursive. It places the
vertices of a given graph on a circle arc, and the edges are drawn as straight segments.
For a given graph G, the procedure nds a bisection witnessing b(G), divides
the given arc into two subarcs, and recursively places the vertices of G 1 on one of the arcs
and the vertices of G 2 on the other arc (here G i is the subgraph induced by V i ).
Let '(G) denote the maximum number of edges going \over" a vertex in the resulting
drawing of G (an edge fu; vg is said to go over a vertex w if u and v lie on the arc on opposite
sides of w). We have the recurrence
and induction then shows that '(G)  C 1 hb(G) log n, where C 1 is a suitable constant.
Now we can prove cr(G)  C log 4
induction on n. Using the drawing produced by the algorithm, we obtain

By estimating '(G 1 ) and '(G 2 ) as above and using the induction hypothesis for G 1 and G 2 ,
we have
The induction step is nished by using hb(G) 2  C 2 log 2 n(pcr(G)+ssqd(G)) from Theorem 2.
This completes the proof of the weaker bound (5). 2
The stronger bound in Theorem 1 is again based on the recursive drawing of the graph
on the circle arc, with two additional ideas. The rst idea is to better split the graph into
two parts: Rather then partitioning the graph into two parts of approximately the same
size, it is more appropriate to partition the graph into two parts with approximately equal
pair-crossing number (see Lemma 6 below). The other improvement is a better method for
counting the crossings in the recursive drawing of G, based on a recent algorithm for crossing
number approximation by Even et al. [3]. Even et al. actually improved the analysis of the
recursive procedure of Bhatt and Leighton for drawing G.
Lemma 6 For every graph G on n vertices there exists a partition
size
log n
such that for
where G i is the subgraph of G induced by V i .
Proof. The idea is to transform the given graph G into a new graph G 0 in such a way that
the number of vertices in G 0 captures both ssqd(G) and pcr(G). Then we get the desired
partition of G by applying Theorem 2 to the new graph G 0 .
We consider a drawing of G optimal with respect to the pair crossing number, and for
an edge e, let p(e) denote the number of pair crossings of this edge. We set a weight w(e) to
p(e)=2, for every edge. For every vertex increase the weight of every adjacent edge
but one by deg(v), and the weight of the last adjacent edge is increased only by deg(v) 1. We
get the new graph G 0 by replacing every edge by a path of length w(e) 1 (in other
words, we add roughly deg(u)+deg(v)+p(e)=2 new vertices on an edge It is easy
to see that ssqd(G 0
and moreover, we can add the new vertices in such a way that Also, a
bisection of G 0 of size m naturally induces a partition of G of size m.
For a subgraph G 0
i of G 0 , let V i denote the set of original vertices in G 0
(that is, those
coming from G), and let G i be the subgraph of G induced by V i . The important observation
is that the number of vertices in G 0
i is an upper bound on pcr(G
there is a bisection of size
log
that separates G 0 into G 0
1 and G 0
2 , and thus we have a partition of G of size O(s)
such that pcr(G i 2. 2
Proof of Theorem 1. Let T denote a binary tree representing a recursive decomposition
of G according to Lemma 6: The root of T corresponds to the set V , and two children of a
vertex associated with a set V t correspond to the two sets
constituting
the partition of V t given by Lemma 6.
An edge of G is split in a tree vertex t if u;
for the
two children t. Let G t denote the subgraph of G induced by V t , and let n
a tree vertex t.
Consider the drawing on the circle arc that is based on the recursive partitioning by
Lemma 6. To bound the number of edge crossings in this drawing, we charge a crossing of
e and e 0 to the rst edge among e and e 0 that was split rst by the partitioning procedure.
It is easy to observe that for any two crossing edges the tree vertex in which the edge
e was split is an ancestor of the tree vertex in which e 0 was split, or the other way round
(by denition, a vertex is an ancestor to itself). In other words, for any tree vertex t with
children the edges in G t 1
do not cross with edges in G t 2
Observation 7 (Even et al. [3]) Let P (u; v) denote the set of vertices in T on the path
from the leaf corresponding to u to the leaf corresponding to v. The number of crossings that
are charged to the edge is bounded by
)j.
By a combination of Observation 7 and Lemma 6, an edge charged for at
most X
log n t
crossings. Since the partitioning procedure guarantees an exponential decrease of pcr(G t
an edge e is charged for at most
O
log n
crossings, where t is the vertex in which e was split. Recalling that the size of the partition
of G t is
O
log n t
the number of crossings for which a tree vertex t is charged is at most
O
log
Since the tree vertices in the same layer form a partition of V and the number of layers
is O(log n), all tree vertices are charged for at most O(log 3
Theorem 1 is proved. 2
It is worth mentioning that balancing the partitions by Lemma 6, that is, with respect
to the pair-crossing number as opposed to the number of vertices, is crucial in the above
proof. We aim at upper bounding the number of crossings in our arc-drawing of G in terms
of pcr(G). To do so, we rely on the relation between pcr(G) and b(G) by Theorem 2, namely
on the relation
ssqd(G)). If we simply used a bisection that is
balanced with respect to the number of vertices but not with respect to ssqd(G
the exponential decrease of cut sizes would not be guaranteed and the bound (6) would
increase by a log n factor.
The following example demonstrates this di-culty. It shows that balancing the partitions
with respect to the number of vertices while upper bounding the size of the cuts by the bound
O(log n
really yield a long sequence of cuts with nondecreasing size:
Let k be such that n=2
log n (we have be a set of n=2 i vertices,
be sets of
vertices each. Let G i be a bipartite
graph on the sets A i , B i with n edges chosen in such a way that

Figure

1: A bad graph for vertex-balanced partitions.
denote the edge set of G i (see Fig. 1). Let E 0 be the set of edges of a complete graph on the
set B k . Consider the graph
It is easy to check that G has (n) vertices and that We observe that
a bisection of G, and moreover, that even pcr(G n A 1 Similarly,
bisections in next levels of the recursive partitioning such that one
of the remaining parts of the graph still has pair crossing number (n 2 ) and each of the
partitions has size n.
5 Small nonplanar subgraphs in graphs with large crossing
number
First we relate the existence of small nonplanar subgraphs to edge expansion.
Theorem 8 Let G be a graph with edge expansion  and maximum degree  such that
su-ciently small absolute constant c > 0. Then there
exists a nonplanar subgraph in G of size O( 1 log n).
In particular, a nonplanar subgraph of size O( 1 log n) exists in bounded degree graphs
with   c 0  log n=
n, for a su-ciently large absolute constant c 0 > 0.
Proof. Let P be the system of paths from the embedding of K n in G guaranteed by
Theorem 4. That is, there is a path of length at most between each
pair of vertices in G, and the maximal number of paths passing through an edge is
O( 1 n log n).
Let us choose an ordered sixtuple distinct vertices from V (G)
at random, all ordered sixtuples having the same probability. Let
3g. Let H be the subgraph induced by the union of these paths. Clearly, H has O(L)
vertices. We want to show that with a positive probability H is a nonplanar subgraph in G.
An obstacle that we have to overcome is that the paths in F may cross at vertices and/or
share edges, and thus that we need not always get a subdivision of K 3;3 .
We introduce the following types of pairs of paths from P (see Fig. 2): A pair (p; q) is
called
disjoint crossing arching tangled

Figure

2: Types of pairs of paths.
disjoint if p and q are vertex disjoint, with the possible exception of a common terminal
vertex;
crossing if p and q have four dierent terminal vertices and they have at least one
common vertex;
arching if p and q have a common terminal vertex, and the other terminal vertex of
one of the paths is an internal vertex of the other path; and
tangled if p and q have a common terminal vertex, the other terminal vertex of p does
not lie on q and vice versa, and p and q cross in at least one other vertex.
We claim: With a positive probability, there are no crossing pairs and no arching pairs
in F .
To prove the claim, we show that the expected number of crossing and arching pairs in
F is strictly smaller than one. The number of paths of P passing through a vertex v is at
most C deg(v), and hence the total number of crossing pairs (p; q) with is at most
xed pair of paths with four distinct terminal
vertices appears in F with probability O(n 4 ), the expected number of crossing pairs in
F is O(C 2 ssqd(G)n 4 n). This can be made smaller than any
prescribed constant, say smaller than 1=4, by choosing the constant c in the assumption of
the theorem su-ciently small.
Next, we consider the arching pairs. To choose an arching pair, we can rst select the
vertex v that is terminal for one of the paths, say q, and internal for the other one, p.
Then p can be chosen in at most C deg(v) ways, and there are only two possibilities of
choosing q (one of the terminal vertices of q is v and the other one is one of the terminal
vertices of p). Hence there are O(C
arching pairs, and each of them has
probability O(n 3 ) of appearing in F . The expected number of arching pairs in F is thus
O(
where -(G) denotes the minimum degree of G, the above estimate for the expected number
of arching pairs is dominated by the earlier bound for the expected number of crossing pairs.
We conclude that the expected number of crossing and arching pairs is smaller than one.
We can thus choose a sixtuple U whose paths form only disjoint and tangled pairs. If
there is no tangled pair in F , then H is a subdivision of K 3;3 . It remains to check that even
if tangled pairs appear in F , H still is nonplanar.
Indeed, suppose that H is planar and F contains tangled pairs. Consider a planar drawing
of H. It denes a drawing of K 3;3 : the vertices of K 3;3 are placed to the vertices of U , and
each edge of K 3;3 is drawn along the corresponding path in the drawing of H. This drawing
is not necessarily planar, but no two vertex-disjoint edges cross in it. But it is well known
that every drawing of K 3;3 in the plane has two vertex-disjoint edges that cross (see, e.g.,
[9]). Hence H is nonplanar and Theorem 8 is proved. 2
Remark. Similarly as in Theorem 4, the terms  1 log n and  1 log n can be replaced
by the
ow number F of G. Then, for bounded degree graphs, the condition F < c
guarantees a nonplanar minor of size O(F ) in G. In a way, this is the best possible in
general: a two-dimensional
n mesh is a planar graph with
ow number
n).
Lemma 9 For every graph G,
where m is the number of edges in G.
Proof. Consider the recursive drawing procedure of G on an arc: in each level use the
minimal bisection to divide the current part H into H 1 and H 2 and recursively draw H 1 on
one side of the arc and H 2 on the other. The depth of the recursion is at most 2 log n, and
thus each edge crosses at most 4  hb(G)  log n other edges, which sums into 2
over all edges. 2
Proof of Theorem 3. Let us consider a graph G with n vertices, m edges, and
By Lemma 9, there is a subgraph G 1 with
log n ). Lemma 5 then yields a
subgraph G 2 on n 2  2
vertices with edge expansion
Applying Theorem 8 to G 2 , we obtain a nonplanar subgraph of size
O
O

mn log 2 n
It remains to check that the assumption of Theorem 8 holds for G 2 , namely that
Using the above lower bound for (G 2 ), it is su-cient to check that
and this follows from the assumption k  C
Theorem 3. 2
6 Open problems
An obvious open problem is to decide whether G. We currently do not
see any good reason why this equality should always hold, and so we believe that it makes
sense to continue the investigation of upper bounds on cr(G) in terms of pcr(G).
A nice problem concerns the pair-crossing number of a constant-degree expander G. While
n)), the method of Theorem 2 cannot yield such lower bound
for pcr(G), since the
ows simply cannot be made su-ciently large. Still, it is very natural
to conjecture that
In Section 5 we proved a lower bound on the edge expansion (of a subgraph) in terms of
the crossing number, using the recursive drawing procedure. Although the resulting bound
is almost tight in some cases (for bounded-degree graphs with quadratic crossing number,
say), perhaps it can be improved for smaller crossing numbers. For example, is it true that
for all k, every graph with maximum degree bounded by a constant contains a subgraph with
edge
expansion
Finally, the crossing number is much less understood for graphs with large degrees than
for those with degrees bounded by a constant. The term ssqd(G) appears very often in
various bounds and, if some degrees are large, it usually makes the bounds uninteresting.
One of the main tools for bounding the crossing number, the recursive procedure of drawing
on an arc by recursive bisection, no longer works in the presence of high degrees: For example,
while K 2;n is planar, any straight-edge drawing with vertices on an arc
has
Further, the bisection width of K 2;n is
n), of the same order as for K 3;n ; the former graph
is planar, while the latter has crossing number
the bisection width is no longer
suitable for estimating the crossing number. It seems that substantial new ideas are needed
for, say, a good approximation algorithm for the crossing number of general graphs.

Acknowledgment

We would like to thank Robert Babilon, Helena Nyklova, Pavel Valtr, and other participants
of a seminar in Prague for useful discussions. We also thank Fahrad Shahrokhi for pointing
out the paper [3] to us, which led to an improvement of Theorem 1.



--R


A framework for solving VLSI graph layout problems.
Improved approximations of crossings in graph drawings.
Improved bounds for the unsplittable ow problem.

Complexity issues in VLSI.
New lower bound techniques for VLSI.
Multicommodity max- ow min-cut theorems and their use in designing approximation algorithms
Graphs on Surfaces.
Applications of the crossing number.



Randomized rounding: A technique for provably good algorithms and algorithmic proofs.



Personal communication.
--TR
Randomized rounding: a technique for provably good algorithms and algorithmic proofs
On VLSI layouts of the star graph and related networks
The book crossing number of a graph
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Which crossing number is it anyway?
Improved bounds for the unsplittable flow problem
Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
Crossing numbers of random graphs
Expander flows, geometric embeddings and graph partitioning
expansion;crossing number;graph drawing;pair-crossing number