### Edge-disjoint routing in plane switch graphs in linear timeEdge-disjoint routing in plane switch graphs in linear time

Access Restriction
Subscribed

 Author Hochstein, Jan M. ♦ Weihe, Karsten Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Planar graphs ♦ Edge-disjoint paths Abstract By a switch graph, we mean an undirected graph $\textit{G}$ = $(\textit{P}$ ⊍ $\textit{W},$ $\textit{E})$ such that all vertices in $\textit{P}$ (the $\textit{plugs})$ have degree one and all vertices in $\textit{W}$ (the $\textit{switches})$ have even degrees. We call $\textit{G}$ $\textit{plane}$ if $\textit{G}$ is planar and can be embedded such that all plugs are in the outer face. Given a set $(s_{1},$ $t_{1}),$ $…,(s_{k},$ $t_{k})$ of pairs of plugs, the problem is to find edge-disjoint paths $p_{1},$ …, $p_{k}$ such that every $p_{i}$ connects $s_{i}$ with $t_{i}.$ The best asymptotic worst-case complexity known so far is quadratic in the number of vertices. In this article, a linear, and thus asymptotically optimal, algorithm is introduced. This result may be viewed as a concluding "keystone" for a number of previous results on various special cases of the problem. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 4 Page Count 35 Starting Page 636 Ending Page 670

#### Open content in new tab

Source: ACM Digital Library