Edge-disjoint routing in plane switch graphs in linear time.

By a switch graph, we mean an undirected graph G = (P ⊍ W, E) such that all vertices in P (the plugs) have degree one and all vertices in W (the switches) have even degrees. We call G plane if G is planar and can be embedded such that all plugs are in the outer face. Given a set (s1, t1),...

Full description

Bibliographic Details

Published in:	Journal of the ACM 51, 4 (2004).
Main Author:	Hochstein, J.M
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Routing and layout. Mathematics of computing. Discrete mathematics. Graph theory. Algorithms. Theory.