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

Authors

  • Michael Bannister
  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00479

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.

Downloads

Download data is not yet available.

Downloads

Published

2018-09-01

How to Cite

Bannister, M., & Eppstein, D. (2018). Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth. Journal of Graph Algorithms and Applications, 22(4), 577–606. https://doi.org/10.7155/jgaa.00479

Issue

Section

Articles

Categories