Alternating Paths and Cycles of Minimum Length

Evans, 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 24-26, 2015 , pp. 383-394(Official URL:

Full text not available from this repository.


Let 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 3-colored point-sets in O(n^2) time with O(n) bends per edge. We also prove that for arbitrary k-colored point-sets, the problem of computing an alternating shortest cycle is NP-hard, where k is any positive integer constant.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item