TITLE:Worst Case Bounds For Shortest Path Interval Routing AUTHORS:Cyril Gavoille and Éric Guévremont ABSTRACT: Consider shortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a network G, let IRS(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes on G. In this paper, we establish tight worst case bounds on IRS(G). More precisely for any n, we construct a network G of n nodes with IRS(G) \in \Theta(n), thereby improving on the best known lower bound of \Omega (n/logn). We also establish a worst case bound on bounded degree networks: for any \Delta >= 3 and any n, we construct a network $G_\Delta$ of n nodes and maximum degree $\Delta$ with IRS(G_\Delta) \in \Omega(n/(logn)2).