TY - GEN
T1 - Orthogonal layout with optimal face complexity
AU - Alam, M. Jawaherul
AU - Kobourov, Stephen G.
AU - Mondal, Debajyoti
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.
PY - 2016
Y1 - 2016
N2 - We study a problem motivated by rectilinear schematization of geographic maps. Given a biconnected plane graph G and an integer k ≥ 0, does G have a strict-orthogonal drawing with at most k reflex angles per face? For k = 0 the problem is equivalent to realizing each face as a rectangle. The problem can be reduced to a max-flow problem in some linear-size nonplanar network, but the best solutions require Ω(n1.5 log n log k) time. We describe a graph matching approach that can decide strict-orthogonal drawability for arbitrary reflex complexity k in O((nk)1.5) time, which is faster for constant values of k. In contrast, if the embedding is not fixed, we prove that it is NP-complete to decide whether a planar graph admits a strict-orthogonal drawing with reflex face complexity 4.
AB - We study a problem motivated by rectilinear schematization of geographic maps. Given a biconnected plane graph G and an integer k ≥ 0, does G have a strict-orthogonal drawing with at most k reflex angles per face? For k = 0 the problem is equivalent to realizing each face as a rectangle. The problem can be reduced to a max-flow problem in some linear-size nonplanar network, but the best solutions require Ω(n1.5 log n log k) time. We describe a graph matching approach that can decide strict-orthogonal drawability for arbitrary reflex complexity k in O((nk)1.5) time, which is faster for constant values of k. In contrast, if the embedding is not fixed, we prove that it is NP-complete to decide whether a planar graph admits a strict-orthogonal drawing with reflex face complexity 4.
UR - http://www.scopus.com/inward/record.url?scp=84956698256&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956698256&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49192-8_10
DO - 10.1007/978-3-662-49192-8_10
M3 - Conference contribution
AN - SCOPUS:84956698256
SN - 9783662491911
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 121
EP - 133
BT - SOFSEM 2016
A2 - Freivalds, Rūsiņš Mārtiņš
A2 - Engels, Gregor
A2 - Catania, Barbara
PB - Springer-Verlag
T2 - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016
Y2 - 23 January 2016 through 28 January 2016
ER -