A FixedParameter Approach to TwoLayer PlanarizationDujmović, Vida and Fellows, M. and Hallett, M. and Kitching, Matthew and Liotta, Giuseppe and McCartin, C. and Nishimura, N. and Ragde, P. and Rosamond, F. and Suderman, Matthew and Whitesides, Sue and Wood, David R. (2002) A FixedParameter Approach to TwoLayer Planarization. In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 115(Official URL: http://dx.doi.org/10.1007/3540458484_1). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_1
AbstractA bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2LAYER PLANARIZATION problem asks if k edges can be deleted from a given graph G so that the remaining graph is biplanar. This problem is NPcomplete, as is the 1LAYER PLANARIZATION problem in which the permutation of the vertices in one layer is fixed. We give the following fixed parameter tractability results: an O(k \centerdot 6^k+G) algorithm for 2LAYER PLANARIZATION and an O(3^k\centerdot G) algorithm for 1LAYER PLANARIZATION, thus achieving linear time for fixed k.
Actions (login required)
