New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

Greg Bodwin, Gary Hoppenworth

For an input graph $G$, an additive spanner is a sparse subgraph $H$ whose shortest paths match those of $G$ up to small additive error. We prove two new lower bounds in the area o…