Geometric spanners with small chromatic number
Public Deposited- Resource Type
- Creator
- 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, there exists a t(k)-spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)-spanner for P that has O(|P|) edges and chromatic number at most k. Finally, we consider an on-line variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
- Language
- Publisher
- Identifier
- Citation
- Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Maheshwari, A, Smid, M, & Zeh, N. (Norbert). (2008). Geometric spanners with small chromatic number. doi:10.1007/978-3-540-77918-6_7
- Date Created
- 2008-08-27
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
|
chromatic-spanners.pdf | 2022-08-26 | Public | Download |