Graph drawing: unrooted undirected tree graphs with specified edge lengths

Question

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

"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.

Answer 1

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:

_{(source: eppstein at www.ics.uci.edu)}