TR-07-15: Geometric Spanners With Small Chromatic Number

Abstract

Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, a t(k)-spanner for P exists that has O(|P|) edges and whose chromatic number is at most k. We prove that t(2) = 3, t(3) = 2, t(4) = √2, and give upper and lower bounds on t(k) for k>4. 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.

TR-07-15.pdf