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.
