Alternating Paths and Cycles of Minimum LengthEvans, William S. and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2015) Alternating Paths and Cycles of Minimum Length. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 383394(Official URL: http://dx.doi.org/10.1007/9783319272610_32). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_32
AbstractLet R be a set of n red points and B be a set of n blue points in the Euclidean plane. We study the problem of computing a planar drawing of a cycle of minimum length that contains vertices at points R∪B and alternates colors. When these points are collinear, we describe a Θ(nlogn)time algorithm to find such a shortest alternating cycle where every edge has at most two bends. We extend our approach to compute shortest alternating paths in O(n^2) time with two bends per edge and to compute shortest alternating cycles on 3colored pointsets in O(n^2) time with O(n) bends per edge. We also prove that for arbitrary kcolored pointsets, the problem of computing an alternating shortest cycle is NPhard, where k is any positive integer constant.
Actions (login required)
