TY - GEN

T1 - Complexity of finding non-planar rectilinear drawings of graphs

AU - Maňuch, Ján

AU - Patterson, Murray

AU - Poon, Sheung Hung

AU - Thachuk, Chris

N1 - Funding Information:
★ Research supported by NSERC Discovery Grant. ★★ Research supported by NSERC PGS-D. ★★★ Research supported by NSC Grant 97-2221-E-007-054-MY3 in Taiwan. † Research supported by NSERC PGS-D and MSFHR Trainee Award.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79952254183&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18469-7_28

DO - 10.1007/978-3-642-18469-7_28

M3 - Conference contribution

AN - SCOPUS:79952254183

SN - 9783642184680

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 305

EP - 316

BT - Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers

T2 - 18th International Symposium on Graph Drawing, GD 2010

Y2 - 21 September 2010 through 24 September 2010

ER -