Layer-Respecting Linear Graph Layouts
This work provides efficient algorithms for a previously NP-hard graph drawing problem, benefiting researchers in graph visualization and computational geometry.
The authors present fixed-parameter tractable linear-time algorithms for minimizing edge crossings in layer-respecting linear graph layouts, where the parameter is the width of a layered graph. They show that the problem, NP-hard for general arc diagrams, becomes tractable under this parameterization.
We show how to visualize a graph, $G=(V,E)$, as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossings, where layer-respecting means that layers appear in order on a single line and vertices are grouped by their layers. Even though this problem is NP-hard for general arc diagrams, we show how to create such diagrams with fixed-parameter tractable linear-time algorithms, where the parameter that allows this is the width of a layered graph. Such a layered graph can be obtained from a breadth-first search (BFS), in which case the width is upper bounded by a graph width parameter called the BFS width.