How to Embed a Path onto Two Sets of Points

Di Giacomo, Emilio and Liotta, Giuseppe and Trotta, Francesco (2006) How to Embed a Path onto Two Sets of Points. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 111-116 (Official URL: http://dx.doi.org/10.1007/11618058_11).

Full text not available from this repository.

Abstract

Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let P be a path such that |R| vertices of P are red and |B| vertices of P are blue. We study the problem of computing a crossing-free drawing of P such that each blue vertex is represented as a point of B and each red vertex of P is represented as a point of R. We show that such a drawing can always be realized by using at most one bend per edge.

Item Type:Conference Paper
Additional Information:10.1007/11618058_11
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.540 Planar
G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.210 Bends
ID Code:685

Repository Staff Only: item control page

References

M. Abellanas, J. Garcia-Lopez, G. Hernández-Penver, M. Noy, and P. A. Ramos. Bipartite embeddings of trees in the plane. Discrete Applied Mathematics, 93(2-3):141-148, 1999.

J. Akiyama and J. Urrutia. Simple alternating path problem. Discrete Mathematics, 84:101-103, 1990.

E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Book-embeddability of series-parallel digraphs. Algorithmica. to appear.

A. Kaneko, M. Kano, and K. Suzuki. Path coverings of two sets of points in the plane. In J. Pach, editor, Towards a Theory of Geometric Graph, volume 342 of Contempory Mathematics. American Mathematical Society, Providence, 2004

A. Kanenko and M. Kano. Discrete geometry on red and blue points in the plane - a survey -. In Discrete and Computational Geometry, volume 25 of Algorithms and Combinatories. Springer, 2003.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.