The Bundled Crossing Number

DOI10.1007/978-3-319-50106-2_31MaRDI QIDQ2961534zbMATH OpenOpenAlexFDO

Authors Md. Jawaherul Alam, Martin Fink, Sergey Pupyrev

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08161, http://hdl.handle.net/10995/102766

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

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 $frac6cc-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 $frac6cc-3$ for graphs with at least $cn$ edges for $c>3$.

Recommendations

• Approximating the bundled crossing number
• Approximating the Bundled Crossing Number
• Crossing numbers
• scientific article; zbMATH DE number 1507304
• Bundled crossings revisited
• Bundled crossings revisited
• On the maximum crossing number
• On the Maximum Crossing Number
• THE ADDITIVITY OF CROSSING NUMBERS
• scientific article; zbMATH DE number 5019924

Cites work

• An algorithm for the graph crossing number problem
• Bundled Crossings in Embedded Graphs
• Coding and counting arrangements of pseudolines
• Computing a canonical polygonal schema of an orientable triangulated surface
• Computing upward topological book embeddings of upward planar digraphs
• Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
• Crossing-Free Subgraphs
• Degenerate crossing numbers
• Edge routing with ordered bundles
• Efficient enumeration of all ladder lotteries and its application
• Graph Drawing
• Graph-Theoretic Concepts in Computer Science
• Hardness of approximation for crossing number
• Improved Circular Layouts
• On the degenerate crossing number
• Ordering metro lines by block crossings
• Strict confluent drawing
• The Bundled Crossing Number
• The Degenerate Crossing Number and Higher-Genus Embeddings
• The genus crossing number
• The graph crossing number and its variants: a survey
• The graph genus problem is NP-complete

Cited in

(12)

• Approximating the bundled crossing number
• Bundled crossings revisited
• The Bundled Crossing Number
• Edge routing with ordered bundles
• Crossing Layout in Non-planar Graph Drawings
• On strict (outer-)confluent graphs
• scientific article; zbMATH DE number 7236457 (Why is no real title available?)
• Bundled crossings revisited
• Approximating the Bundled Crossing Number
• Block crossings in one-sided tanglegrams
• Block crossings in one-sided tanglegrams
• Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

This page was built for publication: The Bundled Crossing Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961534)