On Interval Routing Schemes and Treewidth

In this paper, we investigate which processor networks allow k-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k ≥ 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 contain K_{2, r} as a minor has treewidth at most 2r - 2. As a consequence, graphs that allow k-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k. Similar results are shown for other types of Interval Routing Schemes.