Fixed parameter tractability of crossing minimization of almost-trees
classification
💻 cs.CG
cs.DS
keywords
crossingnumberpagebookminimizationedgesfixedparameter
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.