McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Wednesday, October 13th, 1999
TIME: 16:30-17:30
PLACE: McConnell 320
TITLE: On A Straight-Line Embedding Problem Of Forests.
SPEAKER: Shin-ichi Tokunaga, College of Liberal Arts and Sciences, Tokyo Medical and Dental University.  

Let G a planar graph, and let P be a set of |V(G)| points in the plane in general position (i.e., no three of them are collinear). Then G is said to be stright-line embedded onto P or line embedded onto P if G is embedded in the plane so that each vertex of G corresponds to a distinct point of P and each edge corresponds to a straight-line segment.

In this talk, we consider line embeddings having one more property. Suppose n vertices v_1, v_2,...,v_n of G and n points p_1, p_2,...,p_n of P are specified. Then we say that (G;v_1,v_2,...,v_n) is strongly (resp. weakly) line embedded onto (P;p_1,p_2,...,p_n) if G is line embedded onto P so that for every 1 =< i =< n, v_i corrresponds to p_i (resp. one of {p_1...,p_n}).

As a generalization of M. Perles' rooted tree embedding problem, we show some results concerning the existence of those embeddings defined above in the case where G is a forest whose each component contains one specified vertex.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at