Additive sparse spanners for graphs with bounded length of largest induced cycle

In this paper, we show that every chordal graph with n vertices and m edges admits an additive 4-spanner with at most 2n-2 edges and an additive 3-spanner with at most O(nlogn) edges. This significantly improves results of Peleg and Schäffer from [Graph Spanners, J. Graph Theory 13 (1989) 99-116]. Our spanners are additive and easier to construct. An additive 4-spanner can be constructed in linear time while an additive 3-spanner is constructable in O(mlogn) time. Furthermore, our method can be extended to graphs with largest induced cycles of length k. Any such graph admits an additive (k+1)-spanner with at most 2n-2 edges which is constructable in O(nk+m) time.