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, Los Angeles, CA, USA , 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
ID Code:1504

Repository Staff Only: item control page


Abellanas, M., Garcia-Lopez, J., Hernández-Peñalver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discr. Appl. Math. 93(2–3), 141–148 (1999)

Akiyama, J., Urrutia, J.: Simple alternating path problem. Discr. Math. 84, 101–103 (1990)

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theor. Comput. Sci. 408(2–3), 129–142 (2008)

Bastert, O., Fekete, S.P.: Geometrische Verdrahtungsprobleme. Technical Report 96–247, Universität zu Köln (1996)

Chan, T.M., Hoffmann, H.-F., Kiazyk, S., Lubiw, A.: Minimum length embedding of planar graphs at fixed vertex locations. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 376–387. Springer, Heidelberg (2013)

Frati, F., Glisse, M., Lenhart, W.J., Liotta, G., Mchedlidze, T., Nishat, R.I.: Point-set embeddability of 2-colored trees. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 291–302. Springer, Heidelberg (2013)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. J. Graph Alg. and Appl. 12(1), 29–49 (2008)

Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica 57(4), 796–818 (2010)

Kaneko, A., Kano, M.: Straight-line embeddings of two rooted trees in the plane. Disc. Comp. Geometry 21(4), 603–613 (1999)

Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discr. Appl. Math. 101, 167–175 (2000)

Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane - a survey-. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25. Springer, New York (2003)

Kaneko, A., Kano, M., Suzuki, K.: Path coverings of two sets of points in the plane. In: Pach, J. (ed.) Towards a Theory of Geometric Graph, vol. 342. American Mathematical Society, Providence (2004)

Kaneko, A., Kano, M., Tokunaga, S.: Straight-line embeddings of three rooted trees in the plane. In: Canadian Conference on Computational Geometry, CCCG 1998 (1998)

Kaneko, A., Kano, M., Yoshimoto, K.: Alternating hamilton cycles with minimum number of crossing in the plane. Int. J. Comp. Geometry Appl. 10, 73–78 (2000)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs Comb. 17, 717–728 (2001)

Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theor. Comp. Sci. 4, 237–244 (1977)