Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
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. –  Igor Rivin Jul 23 '13 at 20:14
1  
@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). –  V. Delecroix Jul 23 '13 at 22:37
    
@VDelecroix: the op did not, I am just saying that that would be a more interesting question.... –  Igor Rivin Jul 23 '13 at 23:22
2  
@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. –  Benoît Kloeckner Jul 24 '13 at 7:45
    
@ 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. –  Garabed Gulbenkian Jul 24 '13 at 23:00

An illustration of V. Delecroix's idea, as I understand it...
          LatticeTree

share|improve this answer
    
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. –  The Masked Avenger Jul 24 '13 at 1:24
    
In the above comment, I am assuming the minimum distance between vertices restriction is still in place. –  The Masked Avenger Jul 24 '13 at 1:30
    
Thanks; I forgot about the min distance constraint. Deleted that faulty construction now. –  Joseph O'Rourke Jul 24 '13 at 1:49
    
@ V.Delecroix. Thanks for a very interesting answer. But –  Garabed Gulbenkian Jul 24 '13 at 20:08
1  
@GarabedGulbenkian: All nodes are placed at lattice points of $\mathbb{Z}^2$, and any two lattice points are separated by $\ge 1$. –  Joseph O'Rourke Jul 24 '13 at 21:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.