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 -