The Bundled Crossing NumberAlama, Muhammad Jawaherul and Fink, Martin and Pupyrev, Sergey The Bundled Crossing Number. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 399412(Official URL: http://dx.doi.org/10.1007/9783319501062_31). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_31
AbstractWe study the algorithmic aspect of edge bundling. A bundled crossing in a drawing of a graph is a group of crossings between two sets of parallel edges. The bundled crossing number is the minimum number of bundled crossings that group all crossings in a drawing of the graph. We show that the bundled crossing number is closely related to the orientable genus of the graph. If multiple crossings and selfintersections of edges are allowed, the two values are identical; otherwise, the bundled crossing number can be higher than the genus. We then investigate the problem of minimizing the number of bundled crossings. For circular graph layouts with a fixed order of vertices, we present a constantfactor approximation algorithm. When the circular order is not prescribed, we get a 6c/c−2 approximation for a graph with n vertices having at least cn edges for c>2. For general graph layouts, we develop an algorithm with an approximation factor of 6c/c−3 for graphs with at least cn edges for c>3.
Actions (login required)
