[shiandow]

The first paragraph mentions a linear time graph colouring algorithm. In fact further on they explain that a simple greedy algorithm that goes through the tasks in order of starting time will work. It's fairly easy to prove it does.

Maybe finding the optimal planning given some dependency is harder (though it isn't if you only have some simple requirements), but this is about visualising a Gantt chart, not calculating one.