Collective additive tree spanners for circle graphs and polygonal graphs

摘要

A graph G = (V, E) is said to admit a system ofμcollective additive tree r-spanners if there is a system T (G) of at most μ spanning trees of G such that for any two vertices u, v of G a spanning tree T ∈ T (G) exists such that the distance in T between u and v is at most r plus their distance in G. In this paper, we examine the problem of finding "small" systems of collective additive tree r-spanners for small values of r on circle graphs and on polygonal graphs. Among other results, we show that every n-vertex circle graph admits a system of at most 2 log_(3/2) n collective additive tree 2-spanners and every n-vertex k-polygonal graph admits a system of at most 2 log_(3/2) k + 7 collective additive tree 2-spanners. Moreover, we show that every n-vertex k-polygonal graph admits an additive (k + 6)-spanner with at most 6n-6 edges and every n-vertex 3-polygonal graph admits a system of at most three collective additive tree 2-spanners and an additive tree 6-spanner. All our collective tree spanners as well as all sparse spanners are constructible in polynomial time.