Non-planar square-orthogonal drawing with few-bend edges

Yu An Lin, Sheung Hung Poon

Research output: Journal PublicationArticlepeer-review

Abstract

We investigate square-orthogonal drawings of non-planar graphs with vertices represented as unit grid squares. We present quadratic-time algorithms to construct the square-orthogonal drawings of 5-graphs, 6-graphs, and 8-graphs such that each edge in the drawing contains at most two, two, and three bends, respectively. In particular, the novel analysis method we use to split a vertex so as to build some specific propagation channels in our algorithms is an interesting technique and may be of independent interest. Moreover, we show that the decision problem of determining whether an 8-graph has a square-orthogonal drawing without edge-bends is NP-complete.

Original languageEnglish
Pages (from-to)150-168
Number of pages19
JournalTheoretical Computer Science
Volume554
Issue numberC
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Bend number
  • NP-completeness
  • Non-planar drawing
  • Square-orthogonal drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Non-planar square-orthogonal drawing with few-bend edges'. Together they form a unique fingerprint.

Cite this