Affordable Access

Publisher Website

Geometric spanners with small chromatic number

Authors
Journal
Computational Geometry
0925-7721
Publisher
Elsevier
Publication Date
Volume
42
Issue
2
Identifiers
DOI: 10.1016/j.comgeo.2008.04.003
Keywords
  • Computational Geometry
  • Spanners
  • K-Colorable Graphs
  • Paz Graph
  • Online Algorithm
  • Geometric Graph
Disciplines
  • Computer Science

Abstract

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 , t ( 4 ) = 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 , t ( 3 ) = 1 + 3 , t ( 4 ) = 1 + 2 , and give upper and lower bounds on t ( k ) for k > 4 .

There are no comments yet on this publication. Be the first to share your thoughts.