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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1434

Actions (login required)

View Item