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

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

Mathematics Subject Classification ID

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

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

(20)

• Ranking and drawing in subexponential time
• Orthogonal planarity testing of bounded treewidth graphs
• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• Simultaneous drawing of layered trees
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Comparing trees via crossing minimization
• A linear edge kernel for two-layer crossing minimization
• 2-layer right angle crossing drawings
• On the parameterized complexity of layered graph drawing
• An FPT algorithm for bipartite vertex splitting
• Approximation algorithms for minimizing edge crossings in radial drawings
• 2-Layer Graph Drawings with Bounded Pathwidth
• The slotted online one-sided crossing minimization problem on 2-regular graphs
• Parameterized analysis and crossing minimization problems
• Graph Drawing
• 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?)
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

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)