Network Simplex Algorithm for DAG Layering

This article is committed to the problem of partitioning a directed acyclic graph into layers such that all edges to the same direction. At first we perform an experimental analysis of some of the existing layering algorithm. Then we propose network simplex algorithm based on linear programming to layer a graph. The goal is to minimize the total sum of edge span so that the layered graph has a smaller area than other algorithms.