Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

DOI10.1007/978-3-319-03841-4_30MaRDI QIDQ2867670zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael J. Bannister, David Eppstein, Joseph A. Simons

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.5741

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings.

Recommendations

• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Fixed-parameter tractability of treewidth and pathwidth
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• scientific article; zbMATH DE number 1974113
• Fixed-parameter tractability for the tree assembly problem
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Fixed-parameter tractability and data reduction for multicut in trees
• Fixed-parameter tractability and characterizations of small special treewidth
• Fixed-parameter tractability results for full-degree spanning tree and its dual

Cited in

(17)

• 1-page and 2-page drawings with bounded number of crossings per edge
• Track layouts, layered path decompositions, and leveled planarity
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Parameterized analysis and crossing minimization problems
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Track layout is hard
• k-level crossing minimization is NP-hard for trees
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• A linear edge kernel for two-layer crossing minimization
• An improved fixed-parameter algorithm for one-page crossing minimization
• Exact learning of multitrees and almost-trees using path queries
• Parameterized approaches to orthogonal compaction
• Parameterized algorithms for fixed-order book drawing with few crossings per edge
• Parameterized approaches to orthogonal compaction

This page was built for publication: Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

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