Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded TreewidthBannister, 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.
Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_18
AbstractWe 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.
Actions (login required)
|