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: http://dx.doi.org/10.1007/978-3-319-03841-4_30).

Full text not available from this repository.

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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.999 Others
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 13 Aug 2014 15:48
Last Modified: 13 Aug 2014 15:48
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1387

Actions (login required)

View Item View Item