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.
$\begingroup$
$\endgroup$
asked Jul 23, 2013 at 18:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ Nice answer, however had the OP asked for both an upper bound on the length of an edge, I fear the answer might be less positive. $\endgroup$ Commented Jul 23, 2013 at 20:14
-
1$\begingroup$ @IgorRivin Sorry, I do not see where there is a mention of an upper bound in the question. I agree that if the tree has unbounded valency and you want an upper bound on the length of the edges then the answer is clearly no (because all adjacent vertices belong to a ball of fixed radius). $\endgroup$ Commented Jul 23, 2013 at 22:37
-
$\begingroup$ @VDelecroix: the op did not, I am just saying that that would be a more interesting question.... $\endgroup$ Commented Jul 23, 2013 at 23:22
-
2$\begingroup$ @Igor Rivin: the question you suggest is solved negatively by a counting argument: if there is an upper bound on the length of vertices, for a binary tree of given height you have to put exponentially many vertices in a ball of quadratic area, so that when the height is large enough there must be pairs of points arbitrarily close one to another. $\endgroup$ Commented Jul 24, 2013 at 7:45
-
$\begingroup$ @ V. Delecroix. I apologize. I see what you have done. The vertices of G that represent vertices of T of equal rank lie on rays which originate on the non-negative y-axis and are parallel to the non-negative x-axis. There is enough room on these rays to achieve any lower bound one desires. The y-coordinates of the vertices of G are multiples of the desired lower bound. I was trying to use concentric circles instead of parallel straight lines to contain vertices of equal rank. Now that you have shown me how easily it can be done, I feel stupid for asking the question. $\endgroup$ Commented Jul 24, 2013 at 23:00
$\begingroup$
$\endgroup$
7
An illustration of V. Delecroix's idea, as I understand it...
answered Jul 24, 2013 at 0:18
-
$\begingroup$ I thought about that too. The problem is that the growth of degrees can be super quadratic. Also, you have to allocate circular arc "ahead of time" to avoid edge crossing, or else limit the arcs severely. $\endgroup$ Commented Jul 24, 2013 at 1:24
-
$\begingroup$ In the above comment, I am assuming the minimum distance between vertices restriction is still in place. $\endgroup$ Commented Jul 24, 2013 at 1:30
-
$\begingroup$ Thanks; I forgot about the min distance constraint. Deleted that faulty construction now. $\endgroup$ Commented Jul 24, 2013 at 1:49
-
$\begingroup$ @ V.Delecroix. Thanks for a very interesting answer. But $\endgroup$ Commented Jul 24, 2013 at 20:08
-
1$\begingroup$ @GarabedGulbenkian: All nodes are placed at lattice points of $\mathbb{Z}^2$, and any two lattice points are separated by $\ge 1$. $\endgroup$ Commented Jul 24, 2013 at 21:07