Every graph supports an IRS: Label arbitrary the nodes and select any routing function with simple paths (without loop) to generate the label of the arcs. Because Interval Routing has been investigated to give compact implementation of routing functions, we are interested to find IRS with small compactness.
Using a depth first search for the labeling of nodes, we have the following result:
Trees have a 1-SIRS (by Theorem 2, and also by Theorem 3 considering undirected trees as acyclic digraphs), and thus, by the use of a spanning tree, every graph has a 1-SIRS. This result has been extended:
For the latter result, more details can be found in [Tel94, page 136]. A comparison of the labeling of [SK85] and of [vLT87] is presented in [SML94]. However the result does not hold for linear intervals.
[FG98] derived an O(n2) time algorithm to label graphs supporting 1-LIRS and 1-SLIRS. A simpler algorithm, based on depth first search, is presented in [EMZ97b]. (The time complexity of the latter is not mentioned.) Note that while theorems above provide characterizations nothing is said about the length of the routing paths.