Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

Bannister, Michael J. and Eppstein, David and Simons, Joseph A. (2013) Fixed Parameter Tractability of Crossing Minimization of Almost-Trees. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 340-351(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.999 Others

Actions (login required)

View Item View Item