TITLE: Lower Bounds for Interval Routing on 3-Regular Networks AUTHORS: Cyril Gavoille and Stéphane Pérennès ABSTRACT: Interval Routing was introduced to reduce the size of the routing tables: a rout er finds the direction to forward a message by determining the interval that con tains the destination address of the message, each interval being associated to one particular direction. In this paper, we give lower bounds for the minimum number of intervals per edge needed to achieve shortest path routing for the class of 3-regular networks. We prove a tight lower bound of $\Theta(n)$ intervals for a 3-regular network of order at most $n$. Moreover, for the particular cas e of 3-regular planar networks, we establish a lower bound of $\Omega(\sqrt{n})$ intervals.