Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth

Bannister, Michael J. and Eppstein, David (2014) Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 210-221(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_18).

Full text not available from this repository.

Abstract

We investigate crossing minimization for 1-page and 2-page book drawings. We show that computing the 1-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing 2-page planarity is fixed-parameter tractable with respect to treewidth, and that computing the 2-page crossing number is fixed-parameter tractable with respect to the sum of the number of crossings and the treewidth of the input graph. We prove these results via Courcelle’s theorem on the fixed-parameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_18
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
M Methods > M.999 Others
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:03
Last Modified: 22 May 2015 09:03
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1434

Actions (login required)

View Item View Item