On Interval Routing Schemes and Treewidth

In this paper, we investigate which processor networks allowk-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixedk⩾1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth. We show that every graph that does not containK2,:ras a minor has treewidth at most 2r−2. As a consequence, graphs that allowk-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k. Similar results are shown for other types of Interval Routing Schemes.