Complexity of Finding Non-Planar Rectilinear Drawings of Graphs
Manuch, Jan and Patterson, Murray and Poon, Sheung-Hung and Thachuk, Chris (2011) Complexity of Finding Non-Planar Rectilinear Drawings of Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 305-316 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_28).
Full text not available from this repository.
We study the complexity of the problem of finding non-planar rectilinear drawings of graphs. This problem is known to be NP-complete. We consider natural restrictions of this problem where constraints are placed on the possible orientations of edges. In particular, we show that if each edge has prescribed direction "left" , "right" , "down" or "up" , the problem of finding a rectilinear drawing is polynomial, while finding such a drawing with the minimum area is NP-complete. When assigned directions are "horizontal" or "vertical" or a cyclic order of the edges at each vertex is specified, the problem is NP-complete. We show that these two NP-complete cases are fixed parameter tractable in the number of vertices of degree 3 or 4.
Repository Staff Only: item control page