A faster fixed parameter algorithm for two-layer crossing minimization

DOI10.1016/J.IPL.2016.04.012zbMATH Open1358.68224arXiv1512.05876OpenAlexW2964248282MaRDI QIDQ284334FDOQ284334

Authors: Yasuaki Kobayashi, Hisao Tamaki 

Publication date: 18 May 2016

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)