Interval routing is a space-efficient routing method for computer networks. In this paper, all graphs are assumed to be planar graphs, unless specified otherwise. We prove the existence of an O(D~3 )-IRS on arbitrary graphs whose longest path is bounded by D, where D is the diameter. Together with the result in Theorem 4 of [14], this result implies an O(n~(3/4) )-IRS on arbitrary graphs whose longest path is bounded by (1 + α)D where α is any constant in (0,1), and n the number of nodes in the graph. It was proved in [3] that for some non-planar graphs, there is a lower bound of 3/2D ― 1 on the longest path for any M-IRS, M = O(n/(Dlog n/D) ). Comparing these two results, we conclude that interval routing can perform strictly better in planar graphs.
展开▼
