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 -