Information Technology Reference
In-Depth Information
t
if
ch
2
(
g
)
>
0, and a
bad
neighbor if
ch
2
(
g
)
0. Note that
t
has two distinct
(good/bad) neighbors, for otherwise deg(
A
)=2
<
7
≤
≤
ʴ
(
G
)or
A
is cut vertex
in
M
(
D
).
Step 3: Charging
1
-triangles.
Let
t
be a 1-triangle, let
f
be the distant
neighbor of
t
and let
e
betheedgeof
f
that faces
t
. (a) Every good neighbor of
t
contributes 1
/
6 units of charge to
t
through the
M
-edge that they share. (b) If
after Step 3(a) the charge of
t
is still negative, then
f
contributes 1
/
6 units of
charge to
t
through
e
.
See Fig. 3 for an illustrations of the discharging steps.
t
g
1
f
3
f
1
f
2
t
A
g
2
Fig. 3.
Discharging steps: in Step 1 each of
t
,
g
1
and
g
2
contributes 1
/
3 units of charge
to
A
;inStep2
f
3
contributes 1
/
3 units of charge to
t
; in Step 3(a)
g
2
contributes 1
/
6
units of charge to
t
; and in Step 3(b)
f
3
contributes 1
/
6 units of charge to
t
.
Considering Steps 2 and 3 and Proposition 2, we have the following observa-
tions.
Observation 3.
Let f be a face that contributes charge through one of its M-
edges
[
xy
]
,andletz (resp., w) be the other vertex of f that is adjacent to x (resp.,
y). If x (resp., y) is a crossing point, then denote by
(
X,X
)
(resp.,
(
Y,Y
)
)the
D-edge that contains xz (resp., yw) such that x
∈
[
Xz
]
(resp., y
∈
[
Yw
]
). We
have:
1. f contributes charge through
[
xy
]
exactly once;
2. if f contributes charge through
[
xy
]
in Step 3(a), then one of x and y is a
crossing point and the other is a vertex of D;and
3. if f contributes charge through
[
xy
]
in Step 2 or Step 3(b), then both x and
y are crossings points and f is a distant neighbor of a
0
-or
1
-triangle t.
Furthermore,
[
Xx
]
and
[
Yy
]
intersect at a point q that is a vertex of t,
(
qx
)
and
(
qy
)
do not intersect, and q
=
X
=
Y if t is a
1
-triangle (otherwise, q
is a crossing point).
Recall that our plan was to distribute the initial charge such that the charge
of every original vertex is one third of its degree and the charge of every face is
nonnegative.
