A faster fixed parameter algorithm for two-layer crossing minimization

DOI10.1016/J.IPL.2016.04.012MaRDI QIDQ284334zbMATH OpenOpenAlexFDO

Authors Yasuaki Kobayashi, Hisao Tamaki

Publication date 18 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.05876

zbMATH Keywords

graph algorithmsbipartite crossing numbergraph drawingparameterized algorithmstwo-layer crossing minimization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We give an algorithm that decides whether the bipartite crossing number of a given graph is at most $k$. The running time of the algorithm is upper bounded by $2^{O(k)}+n^{O(1)}$, where $n$ is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in $2^{O(klogk)}+n^{O(1)}$ time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.

Recommendations

• A linear edge kernel for two-layer crossing minimization
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Drawing bipartite graphs in two layers with specified crossings
• Counting edge crossings in a 2-layered drawing
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms

Cites work

• A linear edge kernel for two-layer crossing minimization
• Bipartite permutation graphs
• Crossing Number is NP-Complete
• On bipartite drawings and the linear arrangement problem
• On the complexity of \(k\)-SAT
• On the parameterized complexity of layered graph drawing
• The graph crossing number and its variants: a survey
• The linear arrangement problem parameterized above guaranteed value

Cited in

(17)

• On the one-sided crossing minimization in a bipartite graph with large degrees
• Drawing bipartite graphs in two layers with specified crossings
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• Quantum graph drawing (best student paper)
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• A linear edge kernel for two-layer crossing minimization
• SOFSEM 2005: Theory and Practice of Computer Science
• An SDP approach to multi-level crossing minimization
• A linear edge kernel for two-layer crossing minimization
• Counting edge crossings in a 2-layered drawing
• A variable depth neighborhood search algorithm for the min-max arc crossing problem
• Computing crossing numbers in quadratic time
• Parameterized analysis and crossing minimization problems
• Simple and Efficient Bilayer Cross Counting

This page was built for publication: A faster fixed parameter algorithm for two-layer crossing minimization

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