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 V(0), ... , V(k-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 So, ... ,S(k-1) with vertical bar V(i)vertical bar=vertical bar S(i)vertical bar (0 <= i <= k - 1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of V(i) is mapped to a distinct point of S(i). 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. (C) 2008 Elsevier B.V. All rights reserved.
graph drawing computational geometry point-set embedding graph hamiltonicity