Square-orthogonal drawing with few bends per edge

Yu An Lin; Sheung Hung Poon

doi:10.1007/978-3-642-38768-5_33

Square-orthogonal drawing with few bends per edge

Yu An Lin, Sheung Hung Poon

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
Pages	361-372
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-38768-5_33
Publication status	Published - 2013
Externally published	Yes
Event	19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China Duration: 21 Jun 2013 → 21 Jun 2013

Publication series

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

Conference

Conference	19th International Computing and Combinatorics Conference, COCOON 2013
Country/Territory	China
City	Hangzhou
Period	21/06/13 → 21/06/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-38768-5_33

Cite this

Lin, Y. A., & Poon, S. H. (2013). Square-orthogonal drawing with few bends per edge. In Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings (pp. 361-372). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS). https://doi.org/10.1007/978-3-642-38768-5_33

@inproceedings{e179e259d9d449399bd4b20dab08a1b3,

title = "Square-orthogonal drawing with few bends per edge",

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.",

author = "Lin, {Yu An} and Poon, {Sheung Hung}",

year = "2013",

doi = "10.1007/978-3-642-38768-5_33",

language = "English",

isbn = "9783642387678",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "361--372",

booktitle = "Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings",

note = "19th International Computing and Combinatorics Conference, COCOON 2013 ; Conference date: 21-06-2013 Through 21-06-2013",

}

Lin, YA & Poon, SH 2013, Square-orthogonal drawing with few bends per edge. in Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7936 LNCS, pp. 361-372, 19th International Computing and Combinatorics Conference, COCOON 2013, Hangzhou, China, 21/06/13. https://doi.org/10.1007/978-3-642-38768-5_33

Square-orthogonal drawing with few bends per edge. / Lin, Yu An; Poon, Sheung Hung.
Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings. 2013. p. 361-372 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Square-orthogonal drawing with few bends per edge

AU - Lin, Yu An

AU - Poon, Sheung Hung

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84884915994&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38768-5_33

DO - 10.1007/978-3-642-38768-5_33

M3 - Conference contribution

AN - SCOPUS:84884915994

SN - 9783642387678

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 361

EP - 372

BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings

T2 - 19th International Computing and Combinatorics Conference, COCOON 2013

Y2 - 21 June 2013 through 21 June 2013

ER -

Square-orthogonal drawing with few bends per edge

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this