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

9 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationGraph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
Pages305-316
Number of pages12
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event18th International Symposium on Graph Drawing, GD 2010 - Konstanz, Germany
Duration: 21 Sep 201024 Sep 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

Conference

Conference18th International Symposium on Graph Drawing, GD 2010
Country/TerritoryGermany
CityKonstanz
Period21/09/1024/09/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

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

Cite this