A faster fixed parameter algorithm for two-layer crossing minimization

DOI10.1016/j.ipl.2016.04.012zbMath1358.68224arXiv1512.05876OpenAlexW2964248282MaRDI QIDQ284334

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 algorithmsgraph drawingparameterized algorithmsbipartite crossing numbertwo-layer crossing minimization

Mathematics Subject Classification ID

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

Related Items (3)

Parameterized analysis and crossing minimization problems ⋮ A variable depth neighborhood search algorithm for the min-max arc crossing problem ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

Cites Work

• A linear edge kernel for two-layer crossing minimization
• On the parameterized complexity of layered graph drawing
• 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
• On the complexity of \(k\)-SAT

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