Fixed parameter algorithms for one-sided crossing minimization revisited

DOI10.1016/J.JDA.2006.12.008MaRDI QIDQ935846zbMATH OpenOpenAlexFDO

Authors Vida Dujmović, Henning Fernau, Michael Kaufmann

Publication date 8 August 2008

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2006.12.008

zbMATH Keywords

crossing minimizationgraph drawingparameterized algorithms2-layer drawings\(\mathcal {FPT}\)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Graph Drawing
• 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
• scientific article; zbMATH DE number 1974113
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation

Cites work

• scientific article; zbMATH DE number 2084271 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1875438 (Why is no real title available?)
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A fixed-parameter approach to 2-layer planarization
• A general method to speed up fixed-parameter-tractable algorithms
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Edge crossings in drawings of bipartite graphs
• Graph Drawing
• Kernels: Annotated, Proper and Induced

Cited in

(15)

• 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?)
• 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
• An FPT algorithm for bipartite vertex splitting
• A linear edge kernel for two-layer crossing minimization
• Parameterized analysis and crossing minimization problems
• Drawing (complete) binary tanglegrams
• Graph Drawing
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• Parameterized approaches to orthogonal compaction
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation

This page was built for publication: Fixed parameter algorithms for one-sided crossing minimization revisited

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