Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane - Discrete and Computational Geometry and Graphs - page 96

Properly Colored Geometric Matchings
and 3-Trees Without Crossings
on Multicolored Points in the Plane

B

Mikio Kano 1 , Kazuhiro Suzuki 2(

) , and Miyuki Uno 3

1 Department of Computer and Information Sciences, Ibaraki University,
Hitachi, Ibaraki, Japan
[e-mail]
2 Department of Information Science, Kochi University, Kochi, Japan
[e-mail]
3 University Education Center, Ibaraki University, Mito, Ibaraki, Japan
[e-mail]

Abstract. Let X be a set of multicolored points in the plane such that
no three points are collinear and each color appears on at most |X|/ 2
points. We show the existence of a non-crossing properly colored geomet-
ric perfect matching on X (if |X| is even), and the existence of a non-
crossing properly colored geometric spanning tree with maximum degree
at most 3 on X . Moreover, we show the existence of a non-crossing prop-
erly colored geometric perfect matching in the plane lattice. In order to
prove these our results, we propose an useful lemma that gives a good
partition of a sequence of multicolored points.

· ·

Keywords: Red and blue points Multicolored points Alternating

· · ·

matching Alternating tree Properly colored geometric graph Sequence

of points

MSC2010: 52C35, 05C70, 05C05.

1 Introduction

Various topics on a set of red and blue points in the plane have been studied
[ 3 ]. In this paper, we consider some problems for more colors. Given a set X

of multicolored points in the plane, we want to draw a graph in the plane such
that the vertex set is

and each edge is a straight-line segment whose two end-
vertices have distinct colors. We call such a graph a properly colored geometric

X

M. Kano—Partially supported by Japan Society for the Promotion of Science, Grant-
in-Aid for Scientific Research (C).
K. Suzuki—Partially supported by MEXT. KAKENHI 24740068.
52C35: Arrangements of points, flats, hyperplanes. 05C70: Factorization, matching,
partitioning, covering and packing. 05C05: Trees.