A linear edge kernel for two-layer crossing minimization
From MaRDI portal
Publication:744090
DOI10.1016/j.tcs.2014.06.009zbMath1382.68117OpenAlexW2083110764MaRDI QIDQ744090
Yasuaki Kobayashi, Yusuke Nakae, Hirokazu Maruta, Hisao Tamaki
Publication date: 6 October 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.009
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)
A faster fixed parameter algorithm for two-layer crossing minimization ⋮ Parameterized analysis and crossing minimization problems ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
Cites Work
- Unnamed Item
- Fixed parameter algorithms for one-sided crossing minimization revisited
- On the parameterized complexity of layered graph drawing
- Bipartite permutation graphs
- Edge crossings in drawings of bipartite graphs
- A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
- A fixed-parameter approach to 2-layer planarization
- On Bipartite Drawings and the Linear Arrangement Problem
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- Ranking and Drawing in Subexponential Time
- Crossing Number is NP-Complete
- A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear Edge Kernel for Two-Layer Crossing Minimization
- An SDP approach to multi-level crossing minimization
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On the complexity of \(k\)-SAT
This page was built for publication: A linear edge kernel for two-layer crossing minimization
