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

DOI10.1007/S00453-004-1093-2MaRDI QIDQ1882474zbMATH OpenOpenAlexFDO

Authors Vida Dujmović, Sue 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

FPT Fixed parameter tractabilityGraph drawingLayer crossing minimizationLayer drawingsLevel drawingsNP-completenessSided crossing minimization

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1974113
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Graph Drawing

Cited in

(29)

• Orthogonal planarity testing of bounded treewidth graphs
• The slotted online one-sided crossing minimization problem on 2-regular graphs
• Parameterized analysis and crossing minimization problems
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Ranking and drawing in subexponential time
• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• 2-layer right angle crossing drawings
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• scientific article; zbMATH DE number 7525513 (Why is no real title available?)
• Graph Drawing
• Approximation algorithms for minimizing edge crossings in radial drawings
• An FPT algorithm for bipartite vertex splitting
• 2-Layer Graph Drawings with Bounded Pathwidth
• Simultaneous drawing of layered trees
• Quantum algorithms for one-sided crossing minimization
• Quantum algorithms for one-sided crossing minimization
• Width notions for ordering-related problems
• The PACE 2024 parameterized algorithms and computational experiments challenge: one-sided crossing minimization
• PACE solver description: exact solution of the one-sided crossing minimization problem by the MPPEG team
• PACE solver description: CRGone
• PACE solver description: crossy -- an exact solver for one-sided crossing minimization
• PACE solver description: OCMu64, a solver for one-sided crossing minimization
• Tight runtime bounds for evolutionary algorithms on sorting and crossing minimisation for layered graph drawings
• A linear edge kernel for two-layer crossing minimization
• Fixed parameter algorithms for one-sided crossing minimization revisited
• On the parameterized complexity of layered graph drawing
• Comparing trees via crossing minimization

This page was built for publication: A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1882474)