TITLE:On the Compactness of Bounded Degree Graphs for Shortest Path Interval Routing AUTHORS:Cyril Gavoille and Éric Guévremont ABSTRACT: Consider {\em 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 a worst case bound on $\IRS(G)$. More precisely for every integer $n$ and for every integer $d \geq 3$, we construct a $n$-node network $G$ of maximum degree $d$ with $\IRS(G) = \Omega(n/\log^2{n})$.