Rooted Geometric Forests with Fixed Point-Sets



A geometric graph is a graph drawn in the plane such that a) no three vertices are colinear and b) edges are straight line segments. Edges are allowed to cross, but only transversally at interior points.

Suppose that we are given a forest F of k rooted trees T_1,...,T_k, a set of n points in the plane that are in general position, and an ordered subset p_1,...,p_k of these points.

Problem: Can we find a geometric realization of F with no crossing edges such that the root of T_i is at point p_i. 

Kaneko and Kano [KK1,KK2,KK3] have found such realizations in some special cases, including a) k = 2, b) each tree is a star, and c) all of the trees are of the same size. However, they conjecture that the problem is false in general.

References:

[KK1] A. Kaneko and M. Kano, Straight-line embeddings of two rooted trees in the plane, preprint.

[KK2] A. Kaneko and M. Kano, Straight-line embeddings of rooted star forests in the plane, preprint.

[KK1] A. Kaneko and M. Kano, A balanced partition of points in the plane and tree embedding problems, preprint.
 


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of VermontBurlingtonVT 05401-1455 USA (with thanks to Janos Pach)

Send comments to dan.archdeacon@uvm.edu

December 2003