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

Has Joseph Felsenstein's equal daylight layout been analyzed by the graph drawing community? The following description is taken from his drawtree documentation:

"This iteratively improves an initial tree by successively going to each interior node, looking at the subtrees (often there are 3 of them) visible from there, and swinging them so that the arcs of "daylight" visible between them are equal. This is not as fast as Equal Arc but should never result in lines crossing. It gives particularly good-looking trees, and it is the default method for this program. It will be described in a future paper by me."

Although this description is sufficient for some kind of computer implementation, it probably needs to be fleshed out before it is mathematically appealing. For example, although "swinging a subtree" will not cause edges to cross, it could possibly completely occlude a different vertex so that no daylight reaches it. Additionally it may be reasonable to assume that if two layouts both have equal daylight arcs at every vertex, then the layout with maximal daylight should be preferred. Maybe a generalization of this idea would be a hypothetical criterion like "minimum daylight angular resolution" which would maximize the minimum daylight angle over all vertices of the tree. Other generalizations could look at daylight angles integrated over branches of the drawing, possibly allowing curved edges with constrained arc lengths.

As additional background, here's the drawtree description of a simple equal arc algorithm that draws these edge-distance-constrained trees in a way that can be proved to not depend on the root (up to rotation and translation of the drawing). It has the advantage of being an exact algorithm that runs in finite time, but it has the disadvantage of making subjectively uglier trees than the equal daylight layout:

"This method, invented by Christopher Meacham in PLOTREE, the predecessor to this program, starts from the root of the tree and allocates arcs of angle to each subtree proportional to the number of tips in it. This continues as one moves out to other nodes of the tree and subdivides the angle allocated to them into angles for each of that node's dependent subtrees. This method is fast, and never results in lines of the tree crossing."

One of the few papers that cites equal daylight layout is Improved Layout of Phylogenetic Networks.

A recent graph drawing paper that looks at unrooted tree drawing with edge length constraints is Angle and Distance Constraints on Tree Drawings.

Added: An algorithm suggested in an answer by David Eppstein: Trees with convex faces and optimal angles. The notion of daylight is implicit in this drawing in the sense that every vertex sees daylight. Edge lengths can be set arbitrarily after the angles have been determined, and the properties that edges do not cross and every vertex sees daylight will be preserved.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

I'm not familiar with Felsenstein's work, and the documentation available from the link you give is not very conducive to understanding it: is there no description of what kind of layout algorithms they're using? Or even examples of its output?

However, re: Maybe a generalization of this idea would be a hypothetical criterion like "minimum daylight angular resolution" which would maximize the minimum daylight angle over all vertices of the tree.: I think one of my papers may be relevant for this. See:

"Trees with convex faces and optimal angles." J. Carlson and D. Eppstein. arXiv:cs.CG/0607113. 14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006. Lecture Notes in Comp. Sci. 4372, 2007, pp. 77-88.

It finds tree drawings with the property that, if the leaves are extended to infinity, the result is a decomposition of the plane into convex cells (in particular, every vertex can see out to infinity or, in your terms, every vertex can see daylight) and that the minimum angle between consecutive edges that share a vertex is maximized. It doesn't exactly maximize the minimum daylight angle (that may be zero for some vertices) but I suspect that could be done with minor modifications to the algorithms.

For instance, below is an example of its output; in this example, the optimum vertex angle it finds is a little over π/2:

alt text

share|improve this answer
    
@David: Thanks for your response. I would have linked this paper in my question if it either used the concept of daylight or if it allowed edge length constraint. I agree that the documentation of equal daylight layout is sparse, and I would be very interested to see modifications of your algorithm which include edge distance constraints and the concept of daylight. –  psd Oct 27 '11 at 22:54
    
Edge distance constraints are trivial to add to my algorithm: you can make the edges any length you want and they won't cross each other. –  David Eppstein Oct 27 '11 at 23:23
    
I guess that you can make the edge lengths any length you want and not only will they not cross each other, but the every-vertex-sees-daylight property will also be preserved? –  psd Oct 27 '11 at 23:33
    
Yes, every vertex will continue to see daylight but the angle of some vertices' daylight wedges may shrink to zero as the edges get long. Instead, if you want all opening angles to stay bounded away from zero even in the limit as the leaf edges get very long relative to the rest of the drawing, just use a similar style drawing in which the leaf edges' slopes are all equally spaced around the circle of possible slopes. –  David Eppstein Oct 28 '11 at 1:48
    
I've edited the question to mention these interesting properties of your algorithm. If leaf edge slopes are equally spaced then the terminal fork angles will be small $(2 pi / n)$ when there are $n$ leaves. –  psd Oct 28 '11 at 3:03
add comment

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.