October 17, Wednesday
12:00 – 14:00
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(n \log 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.