Collective additive tree spanners for circle graphs and polygonal graphs

A graph G=(V,E)G=(V,E) is said to admit a system of μμ collective additive tree rr-spanners if there is a system T(G)T(G) of at most μμ spanning trees of GG such that for any two vertices u,vu,v of GG a spanning tree T∈T(G)T∈T(G) exists such that the distance in TT between uu and vv is at most rr plus their distance in GG. In this paper, we examine the problem of finding “small” systems of collective additive tree rr-spanners for small values of rr on circle graphs and on polygonal graphs. Among other results, we show that every nn-vertex circle graph admits a system of at most 2log32n collective additive tree 2-spanners and every nn-vertex kk-polygonal graph admits a system of at most 2log32k+7 collective additive tree 2-spanners. Moreover, we show that every nn-vertex kk-polygonal graph admits an additive (k+6)(k+6)-spanner with at most 6n−66n−6 edges and every nn-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.