Bi-Chromatic point set embeddings of trees with fewer bends

Abstract

Let G be a planar graph such that each vertex in G is colored by either red or blue color. Assume that there are nr red vertices and nb blue vertices in G. Let 8 be a set of fixed points in the plane such that 181 = nr + nb where nr points in 8 are colored by red color and nb points in S are colored by blue color. A bichromatic point-set embedding of G on 8 is a crossing free drawing of G such that each red vertex in G is mapped to a red point in 8 and each blue vertex in G is mapped to a blue point in 8 and each edge is drawn as a polygonal curve. In this thesis, we study the problem of computing bichromatic point-set embeddings of trees with fewer bends per edge on some special configurations of point-sets. Let 8 be such that no two points in 8 have same x-coordinates. Assume an ordering I of the points in 8 by increasing x-values. 8 is called a consecutive point-set when all the points of same color appear consecutively in I. 8 is called an alternating point-set when red and blue points alternate in l. In this thesis, we show that any tree G has a bichromatic point-set embedding on a point set 8 with at most one bend per edge if 8 is either a consecutive point-set or an alternating point-set and such an embedding can be found in linear time.