Square-orthogonal drawing with few bends per edge

Yu An Lin, Sheung Hung Poon

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


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
Title of host publicationComputing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
Number of pages12
Publication statusPublished - 2013
Externally publishedYes
Event19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China
Duration: 21 Jun 201321 Jun 2013

Publication series

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


Conference19th International Computing and Combinatorics Conference, COCOON 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)


Dive into the research topics of 'Square-orthogonal drawing with few bends per edge'. Together they form a unique fingerprint.

Cite this