Longest Path Algorithm for Layer Assignment

Question

I'm working on a program to generate an organizational chart of a company. I have been reading about the longest path algorithm to layer the vertices, and one thing has been bugging me. The reading that I have done suggests that the graph should be layered from the bottom up, starting with placing the nodes with no children on the bottom layer and then working up. However, I have also read that the longest path algorithm leads to graphs with very wide bottoms.

I was thinking that I would try building the graph from the top down, starting with the nodes that have no parents and working my way down. Maybe this is common and I just haven't seen it used, but I am worried that there is some reason that I am not seeing that makes this approach impractical. Is there something I'm missing?

Answer 1

The longest path algorithm minimizes height but essentially ignores width. If you layer the graph from the bottom-up and the graph has many sinks (vertices with zero out-degree) then you will get a wide bottom layer. If you layer the graph from the top-down and it has many sources (vertices with zero in-degree) then you will get a wide top layer. If you compare the number of sinks against the number of sources, you can choose which variant to use. However, you may still get wide intermediate layers. To reduce (not minimize) the width over all layers you need to look at an algorithm like the Coffman-Graham algorithm.