Spoiler Alert: The initial kernel for Graphviz was the attempt to draw graphs related to software engineering. Stephen came across a paper addressing this and, being researchers, of course it was decided we could do better. The obvious choice was to minimize the total sum of discrete edge lengths. After working through many, many examples by hand, we discovered that the problem had some amazing properties and an elegant algorithm. Finally turning to the literature, we found that we had “discovered” that the problem was amenable to a network simplex algorithm, which we had largely reinvented for this particular case. This approach to node ranking turned out to be very effective for directed graph layout.
So much for the y coordinates. Handling the assignment of x coordinates proved a much harder problem, with trying to straighten long edges and maintaining the ordering of nodes in rows while avoiding overlap. The initial techniques involved a bunch of heuristics, each handling one set of constraints. It turned out to be the classic case of competing heuristics, where you improve one only to see another one worsen. Then Stephen recognized that you could rotate the problem ninety degrees and reformulate everything as another network simplex minimization. The only snag was the need to handle absolute values in the objective function, but it turned out there is a standard trick for dealing with this. Thus, a bunch of ad hoc computations could be replaced by a single model which could be solved using the same algorithm used in node ranking. I view this as one of the most beautiful ideas in Graphviz.