A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation

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

zbMATH Keywords

NP-completenessGraph drawingFPT Fixed parameter tractabilityLayer crossing minimizationLayer drawingsLevel drawingsSided crossing minimization

Mathematics Subject Classification ID

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