  We formalize the simplification of activity-on-edge graphs used for
visualizing project schedules, where the vertices of the graphs represent
project milestones, and the edges represent either tasks of the project or
timing constraints between milestones. In this framework, a timeline of the
project can be constructed as a leveled drawing of the graph, where the levels
of the vertices represent the time at which each milestone is scheduled to
happen. We focus on the following problem: given an activity-on-edge graph
representing a project, find an equivalent activity-on-edge graph (one with the
same critical paths) that has the minimum possible number of milestone vertices
among all equivalent activity-on-edge graphs. We provide a polynomial-time
algorithm for solving this graph minimization problem.
