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 , pp. 305-316(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_28).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_28
Classifications: P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1216

Actions (login required)

View Item View Item