Crossing Minimization for 1page and 2page Drawings of Graphs with Bounded TreewidthBannister, Michael J. and Eppstein, David (2014) Crossing Minimization for 1page and 2page Drawings of Graphs with Bounded Treewidth. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 210221(Official URL: http://dx.doi.org/10.1007/9783662458037_18). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_18
AbstractWe investigate crossing minimization for 1page and 2page book drawings. We show that computing the 1page crossing number is fixedparameter tractable with respect to the number of crossings, that testing 2page planarity is fixedparameter tractable with respect to treewidth, and that computing the 2page crossing number is fixedparameter 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 fixedparameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth.
Actions (login required)
