Information Technology Reference
In-Depth Information
3.2 A Proof that
e
3
(
n
)
≤
6(
n −
2)
Suppose that
G
is a graph with
n>
2 vertices that can be drawn such that every
edge crosses at most three other edges (possibly several times), and let
D
be a
drawing of
G
as a topological graph with that property and the least possible
number of crossings.
We prove that
G
hasatmost6
n
−
12 edges by induction on
n
.For
n
≤
10 we
≤
2
and thus the theorem trivially holds. Therefore, we assume
have 6
n
−
12
that
n
11. Furthermore, we may assume that the degree of every vertex in
G
is at least 7, for otherwise the theorem easily follows by removing a vertex of
small degree and applying induction.
We denote by
M
(
D
) the plane map induced by
D
. That is, the vertices of
M
(
D
) are the vertices and crossing points in
D
, and the edges of
M
(
D
)arethe
crossing-free segments of the edges of
D
(where each such edge-segment connects
two vertices of
M
(
D
)). If a certain vertex of
M
(
D
) is known to be a vertex of
D
we will denote it by a capital letter, otherwise, we will use small letters. Unless
the context is clear, we will refer to edges of
D
as
D
-edges and to edges of
M
(
D
)
as
M-edges
. An edge-segment will be denoted by a concatenation of its endpoints
(no comma in between), where round or square brackets will indicate whether
an endpoint is included in the edge-segment. E.g., [
xy
) is an edge-segment whose
endpoints are
x
and
y
, such that
x
is included in [
xy
)and
y
is not. In all the
following figures bold edge-segments mark
M
-edges.
≥
Proposition 1.
If M
(
D
)
is not
2
-connected, then D has at most
6
n
−
12
edges.
By Proposition 1, we may assume henceforth that
M
(
D
) is 2-connected. The
boundary
of a face
f
in
M
(
D
) consists of all the
M
-edges that are incident to
f
.Since
M
(
D
) is 2-connected, the boundary of every face in
M
(
D
)isasimple
cycle. Thus, we can define the
size
of a face
f
,
,asthenumberof
M
-edges
on its boundary. It can be shown that if
M
(
D
) contains a face of size two, then
there is a drawing of
G
as a topological with fewer crossings than
D
and such
that every edge crosses at most three other edges. Therefore, the size of every
face in
M
(
D
) is at least three.
We use the
Discharging Method
(see, e.g., [5]) to prove that
|
f
|
2).
We begin by assigning a
charge
to every face of the planar map
M
(
D
) such that
the total charge is 4
n
|
E
(
D
)
|≤
6(
n
−
8. Then, we redistribute the charge in several steps such
that eventually the charge of every face is nonnegative and the charge of every
vertex
A
−
=
A∈V
(
D
) 3
deg(
A
)
V
(
D
)is
3
deg(
A
). Hence,
3
|
∈
E
(
D
)
|
≤
4
n
−
8
and we get the desired bound on
|
E
(
D
)
|
. Next we describe the proof in details.
Charging.
Let
V
,
E
,and
F
denote the vertex, edge, and face sets of
M
(
D
),
respectively. For a face
f
∈
F
we denote by
V
(
f
) the set of vertices of
D
that are
incident to
f
. It is easy to see that
f∈F
|V
(
f
)
|
=
A∈V
(
D
)
deg(
A
)andthat
f∈F
|
=
u∈V
deg(
u
). Note also that every vertex in
V
\
E
|
f
|
=2
|
V
(
D
)is
a crossing point in
D
and therefore its degree in
M
(
D
) is four. Hence,
|V
(
f
)
|
=
A∈V
(
D
)
deg(
A
)=
u∈V
deg(
u
)=2
|E
|−
4
|V
|−n
.
deg(
u
)
−
f∈F
u∈V
\V
(
D
)