Bundled Crossings Revisited
Journal of Graph Algorithms & Applications, (2020)DOI: 10.7155/jgaa.00535
Abstract
An effective way to reduce clutter in a graph
drawing that has (many) crossings is to group edges
that travel in parallel into bundles. Each edge can
participate in many such bundles. Any crossing in
this bundled graph occurs between two bundles, i.e.,
as a bundled crossing. We consider the problem of
bundled crossing minimization: A graph is given and
the goal is to find a bundled drawing with at most
$k$ bundled crossings. We show that the problem is
NP-hard when we require a simple drawing. Our main
result is an FPT algorithm (in $k$) for simple
circular layouts where vertices must be placed on a
circle and edges must be drawn inside the
circle. These results make use of the connection
between bundled crossings and graph genus. We also
consider bundling crossings in a given drawing, in
particular for storyline visualizations.
