Let G be a planar graph with n vertices whose vertex set is partitioned into subsets V 0, ..., 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 0, ..., 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].
Drawing Colored Graphs on Colored Points
DI GIACOMO, Emilio;LIOTTA, Giuseppe
2007
Abstract
Let G be a planar graph with n vertices whose vertex set is partitioned into subsets V 0, ..., 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 0, ..., 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].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
