Information Technology Reference
In-Depth Information
of
with black. Then there exists the desired Perfect Matching by applying
Theorem
1.6
to
K
.
Hence, we may assume that
W ∪ K
|C|≤n −
1
for every
C ∈{R, B, G}.
The
rectangular hull
of
X
is the smallest closed rectangular enclosing
X
.We
denote by
rect
(
X
) the boundary of the rectangular hull of
X
. We call a point in
X ∩ rect
).
Suppose that some two adjacent vertices
(
X
)a
vertex
on
rect
(
X
u
and
v
on
rect
(
X
) have distinct
colors. By our assumption, we have
|C ∩
(
X −{u, v}
)
|≤|C|≤n −
1
for every
C ∈{R, B, G}.
Thus, since
|X −{u, v}|
=2(
n −
1), we can apply the inductive hypothesis to
X −{u, v}
and there exists a Perfect Matching on
X −{u, v}
. By adding an
L
-
line segment
uv
on
rect
(
X
) to this matching, we can obtain the desired Perfect
Matching.
Therefore, we may assume that all the vertices on
rect
(
X
) have the same
color. Let
a
and
b
be the left and the right vertices on
rect
(
X
), respectively. We
X
sort all the points of
by their horizontal coordinate, and denote the sorted
x
1
,x
2
,...,x
2
n
)sothat
x
1
=
a
x
2
n
=
b
sequence by (
and
. Since the two end-
points
x
1
and
x
2
n
have the same color, by Lemma
1.8
, there exists an even
number
p
(2
≤ p ≤
2
n −
1) such that for every
C ∈{R, B, G}
,
2
|C ∩{x
1
,...,x
p
}| ≤
2
,
n − p
2
|C ∩{x
p
+1
,...,x
2
n
}| ≤
.
This implies that the vertical line passing through
x
p
partitions
X \{x
p
}
into
Left
=
{x
1
(=
a
)
,x
2
,...,x
p−
1
}
and
Right
=
{x
p
+1
,...,x
2
n−
1
,x
2
n
(=
b
)
}
so that
a ∈ Left
,
b ∈ Right
,
|Left ∪{x
p
}|
=
p
,
|Right|
=2
n − p
,andforevery
C ∈{R, B, G}
,
2
|≤
2
,
n − p
2
|C ∩
(
Left ∪{x
p
}
)
|C ∩ Right|≤
.
Since
p
is even, by applying the inductive hypothesis to each of
Left ∪{x
p
}
and
Right
, we can obtain the desired Perfect Matching.
References
1. Hoffmann, M., Toth, C.D.: Vertex-colored encompassing graphs. Graphs and Com-
binatorics
30
, 933-947 (2014)
2. Kaneko, A.: On the maximum degree of bipartite embeddings of trees in the plane.
In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp.
166-171. Springer, Heidelberg (2000)
Search WWH ::
Custom Search