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 also show that every graph that does not contain K 2,r as a minor has treewidth at most 2r - 2. In case the graph is planar, this bound can be lowered to r + 2. As a consequence, graphs that allow k-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k, and treewidth at most 2k + 3 if they are planar. Similar results are shown for other types of Interval Routing Schemes. # This research was partially supported by the ESPRIT Basic Actions Program of the EC under contract No. 8141 (project ALCOM II). The researc..