Complexity of finding non-planar rectilinear drawings of graphs

Ján Maňuch, Murray Patterson, Sheung Hung Poon, Chris Thachuk

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

10 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationGraph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
Number of pages12
Publication statusPublished - 2011
Externally publishedYes
Event18th International Symposium on Graph Drawing, GD 2010 - Konstanz, Germany
Duration: 21 Sept 201024 Sept 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6502 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Symposium on Graph Drawing, GD 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Complexity of finding non-planar rectilinear drawings of graphs'. Together they form a unique fingerprint.

Cite this