The Bundled Crossing Number

Alama, 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. 399-412(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_31).

Full text not available from this repository.

Abstract

We 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 self-intersections 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 constant-factor 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.120 Circular
P Styles > P.999 Others
URI: https://gdea.graphdrawing.org/id/eprint/1558

Actions (login required)

View Item View Item