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. © 2011 Springer-Verlag

Maňuch, J., Patterson, M., Poon, S., Thachuk, C. (2011). Complexity of finding non-planar rectilinear drawings of graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.305-316). SPRINGER-VERLAG BERLIN [10.1007/978-3-642-18469-7_28].

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

#### 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. © 2011 Springer-Verlag
##### Scheda breve Scheda completa Scheda completa (DC) paper
Theoretical Computer Science; Computer Science (all)
English
International Symposium on Graph Drawing, GD 2010 21-24 September
2010
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-364218468-0
2011
6502
305
316
open
Maňuch, J., Patterson, M., Poon, S., Thachuk, C. (2011). Complexity of finding non-planar rectilinear drawings of graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.305-316). SPRINGER-VERLAG BERLIN [10.1007/978-3-642-18469-7_28].
File in questo prodotto:
File
complexity_2010.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 277.81 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/217381`
• 10
• 3