Information Technology Reference
In-Depth Information
A Crossing Lemma for the Pair-Crossing
Number
Eyal Ackerman
1
and Marcus Schaefer
2
Dept. Math., Physics, and Comp. Sci., University of Haifa at Oranim, Tivon, Israel
ackerman@sci.haifa.ac.il
School of Computing, DePaul University, Chicago, Illinois 60604, USA
mschaefer@cdm.depaul.edu
Abstract.
The
pair-crossing number
of a graph
G
,pcr(
G
), is the min-
imum possible number of pairs of edges that cross each other (possibly
several times) in a drawing of
G
. It is known that there is a constant
c ≥
1
/
64 such that for every (not too sparse) graph
G
with
n
vertices
and
m
edges pcr(
G
)
≥ c
m
3
n
2
. This bound is tight, up to the constant
c
.
Here we show that
c ≥
1
/
34
.
2if
G
is drawn without adjacent crossings.
1 Introduction
Throughout this paper we consider graphs with no loops or parallel edges. A
topological graph
is a graph drawn in the plane with its vertices as distinct
points and its edges as Jordan arcs that connect the corresponding points and
do not contain any other vertex as an interior point. Every pair of edges in
a topological graph has a finite number of intersection points. If every pair of
its edges intersect at most once, then a topological graph is called
simple
.The
intersection point of two edges is either avertexthatiscommontobothedges,
or a crossing point at which one edge passes from one side of the other edge to
its other side.
A
crossing
in a topological graph consists of a pair of crossing edges and
a point in which they cross. The
crossing number
of a graph
G
,cr(
G
), is the
minimum possible number of crossings in a drawing of
G
as a topological graph
in the plane. The
pair-crossing number
of a graph
G
,pcr(
G
), is the minimum
possible number of
pairs
of crossing edges in a drawing of
G
as a topological
graph in the plane. There has been some confusion between these two notions in
the literature, probably due to the fact that in a drawing with the least number of
crossings no pair of edges intersects more than once. Perhaps for the same reason
there has also been some confusion as to whether adjacent crossings are allowed
or counted.
1
For examples and history of this confusion and other variants of
the crossing number, see the recent survey of Schaefer [14] and the paper titled
“Which crossing number is it anyway?” by Pach and Toth [12].
Considering adjacent crossings, Pach and Toth [11] introduced the following
notation:
1
By adjacent crossings we mean crossings between edges that share a common vertex.
