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 -