cs.DS
Simplifying Activity on Edge Graphs. 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.