Drawing colored graphs on colored points

Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V0,…,Vk−1 for some positive integer 1≤k≤n. Let S be a set of n distinct points in the plane with a partition into subsets S0,…,Sk−1 with |V|=|S| (0≤i≤k−1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of Vi is mapped to a distinct point of Si. Lower and upper bounds on the number of bends per edge are proved for any 2≤k≤n. In the special case k=n, we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717–728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest.