Abstract:

The talk will be on Geometric Spanners With Small Chromatic number.
Two variants of this problem will be discussed.

Variant 1:
Given a complete k-partite geometric graph K whose vertex set is a set
of n points in $\R^d$, compute a spanner of K that has a "small" stretch
factor and "few" edges.
We present two algorithms for this problem. The first algorithm computes
a $(5+\epsilon)$-spanner of K with O(n) edges in O(n log n) time. The
second algorithm computes a $(3 + \epsilon)$-spanner of K with O(n log n)
edges in O(nlog n) time.
The latter result is optimal: We show that there exist complete k-partite
geometric graphs K such that every subgraph of K with a subquadratic number 
of edges has stretch factor at least 3.

Variant 2:
Given an integer $k > 1$, we consider the problem of computing the smallest
real number $t(k)$ such that for each set $P$ of points in the plane, there
exists a $t(k)$-spanner for $P$  that has a chromatic number at most $k$.
We prove that $t(2) = 3$, $t(3) = 2$, $t(4) = \sqrt{2}$, and give upper and
lower bounds on $t(k)$ for $k>4$. We also show that for any $\epsilon >0$, 
there exists a $(1+\epsilon)t(k)$-spanner for $P$ that has $O(|P|)$ edges 
and whose chromatic number is at most $k$.
We also consider an on-line variant of the problem, in which the points of
$P$ are given one after another, and the color of a point must be decided at 
the moment the point is given.