Let T be a tree which satisfies the following conditions. (A) The set of vertices of T is denumerably infinite. (B) Each vertex of T is an end-point of at most finitely many edges of T. Does there always exist a planar graph G which is isomorphic to T and which satisfies the following conditions? (1) Every edge of G is a straight line segment. (2) No distinct pair of edges of G can have a point in common that is not an end-point of both. (3) The set of distances between distinct pairs of vertices of G has a positive lower bound. ........... The answer to my question seems to be "Yes" if T is a binary tree, but I suspect that the answer might be "No" if the number of edges of T which can meet in the same vertex becomes unbounded.
The answer is clearly yes.
Pick a vertex and choose it as a root. Put it at (0,0). Then put its children at (0,1), (1,1), ..., (n1,1). Then for each of these vertices put their children at (0,2), (1,2), ..., (n2,2) (in doing so make first appear the children of (0,1), then the one of (1,1) etc). Then repeat the same construction for the next stage.
You can join the adjacent vertices with straight line segments. Edges will not cross and the positive lower bound between vertices is 1.
|show 1 more comment|
An illustration of V. Delecroix's idea, as I understand it...
|show 2 more comments|