Drawing Colored Graphs on Colored Points

摘要

Let G be a planar graph with n vertices whose vertex set is partitioned into subsets Vo,…, V_(k-1) for a positive integer 1 ≤ k ≤ n and let S be a set of n distinct points in the plane partitioned into subsets S_o,…,S_(k-1) with |V_i| = |S_i| (0 ≤ i ≤ k - 1). This paper studies the problem of computing a crossing-free 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 3 ≤ k ≤ n. As a special case, we improve the upper and lower bounds presented in a paper by Pach and Wenger for k = n [Graphs and Combinatorics (2001), 17:717-728].