Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/102766
Title: | The bundled crossing number |
Authors: | Alam, M. J. Fink, M. Pupyrev, S. |
Issue Date: | 2016 |
Publisher: | Springer Verlag |
Citation: | Alam M. J. The bundled crossing number / M. J. Alam, M. Fink, S. Pupyrev. — DOI 10.1007/978-3-319-50106-2_31 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2016. — Vol. 9801 LNCS. — P. 399-412. |
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. © Springer International Publishing AG 2016. |
Keywords: | APPROXIMATION ALGORITHMS DRAWING (GRAPHICS) VISUALIZATION ALGORITHMIC ASPECTS APPROXIMATION FACTOR CONSTANT-FACTOR APPROXIMATION ALGORITHMS CROSSING NUMBER MINIMIZING THE NUMBER OF MULTIPLE CROSSINGS ORIENTABLE GENUS SELF-INTERSECTIONS GRAPH THEORY |
URI: | http://elar.urfu.ru/handle/10995/102766 |
Access: | info:eu-repo/semantics/openAccess |
SCOPUS ID: | 85007303442 |
PURE ID: | 1455378 3469f9cf-cddf-4603-8a50-6d7cf2f88ac7 |
ISSN: | 3029743 |
ISBN: | 9783319501055 |
DOI: | 10.1007/978-3-319-50106-2_31 |
Appears in Collections: | Научные публикации, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2-s2.0-85007303442.pdf | 637,17 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.