A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
From MaRDI portal
Publication:1882474
DOI10.1007/s00453-004-1093-2zbMath1082.68589OpenAlexW1978321932MaRDI QIDQ1882474
Vida Dujmović, S. H. Whitesides
Publication date: 1 October 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-004-1093-2
NP-completenessGraph drawingFPT Fixed parameter tractabilityLayer crossing minimizationLayer drawingsLevel drawingsSided crossing minimization
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10)
Related Items (14)
The slotted online one-sided crossing minimization problem on 2-regular graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ An FPT algorithm for bipartite vertex splitting ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ 2-layer right angle crossing drawings ⋮ Fixed parameter algorithms for one-sided crossing minimization revisited ⋮ Ranking and Drawing in Subexponential Time ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization ⋮ On the parameterized complexity of layered graph drawing ⋮ Comparing trees via crossing minimization ⋮ Approximation algorithms for minimizing edge crossings in radial drawings ⋮ A linear edge kernel for two-layer crossing minimization ⋮ Orthogonal planarity testing of bounded treewidth graphs
This page was built for publication: A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
