Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 279–308, 2011.

Abstract:

LetGbe a plane graph with non-negative edge weights, and letkterminal pairs be specified onhface boundaries. We present an algorithm to findknon-crossing walks inGof minimum total length that connect all terminal pairs, if any such walks exist, in 2^{O(h²)}nlogktime. The computed walks may overlap but may not cross each other or themselves. Our algorithm generalizes a result of Takahashi, Suzuki, and Nikizeki [Algorithmica 1996] for the special caseh≤2. We also describe an algorithm for the corresponding geometric problem, where the terminal points lie on the boundary of h polygonal obstacles of total complexityn, in 2^{O(h²)}ntime, generalizing an algorithm of Papadopoulou [IJCGA 1999] for the special caseh≤2. In both settings, shortest non-crossing walks can have complexity exponential inh. We also describe algorithms to determine in O(n) time whether the terminal pairs can be connected byanynon-crossing walks.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012