| 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.