TY - GEN
T1 - Smooth orthogonal drawings of planar graphs
AU - Alam, Muhammad Jawaherul
AU - Bekos, Michael A.
AU - Kaufmann, Michael
AU - Kindermann, Philipp
AU - Kobourov, Stephen G.
AU - Wolff, Alexander
N1 - Funding Information: Research of M.J. Alam and S.G. Kobourov is supported in part by NSF grants CCF-1115971 and DEB 1053573. The work of M.A. Bekos is implemented within the framework of the Action “Supporting Postdoctoral Researchers” of the Operational Program “Education and Lifelong Learning” (Action’s Beneficiary: General Secretariat for Research and Technology), and is co-financed by the European Social Fund (ESF) and the Greek State. M. Kaufmann as well as Ph. Kindermann and A. Wolff acknowledge support by the ESF EuroGIGA project GraDR (DFG grants Ka 812/16-1 and Wo 758/5-1, respectively).
PY - 2014
Y1 - 2014
N2 - In smooth orthogonal layouts of planar graphs, every edge is an alternating sequence of axis-aligned segments and circular arcs with common axis-aligned tangents. In this paper, we study the problem of finding smooth orthogonal layouts of low edge complexity, that is, with few segments per edge. We say that a graph has smooth complexity k - for short, an SC k -layout - if it admits a smooth orthogonal drawing of edge complexity at most k. Our main result is that every 4-planar graph has an SC2-layout. While our drawings may have super-polynomial area, we show that for 3-planar graphs, cubic area suffices. We also show that any biconnected 4-outerplane graph has an SC1-layout. On the negative side, we demonstrate an infinite family of biconnected 4-planar graphs that require exponential area for an SC 1-layout. Finally, we present an infinite family of biconnected 4-planar graphs that do not admit an SC1-layout.
AB - In smooth orthogonal layouts of planar graphs, every edge is an alternating sequence of axis-aligned segments and circular arcs with common axis-aligned tangents. In this paper, we study the problem of finding smooth orthogonal layouts of low edge complexity, that is, with few segments per edge. We say that a graph has smooth complexity k - for short, an SC k -layout - if it admits a smooth orthogonal drawing of edge complexity at most k. Our main result is that every 4-planar graph has an SC2-layout. While our drawings may have super-polynomial area, we show that for 3-planar graphs, cubic area suffices. We also show that any biconnected 4-outerplane graph has an SC1-layout. On the negative side, we demonstrate an infinite family of biconnected 4-planar graphs that require exponential area for an SC 1-layout. Finally, we present an infinite family of biconnected 4-planar graphs that do not admit an SC1-layout.
UR - https://www.scopus.com/pages/publications/84899932789
UR - https://www.scopus.com/pages/publications/84899932789#tab=citedBy
U2 - 10.1007/978-3-642-54423-1_13
DO - 10.1007/978-3-642-54423-1_13
M3 - Conference contribution
SN - 9783642544224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 144
EP - 155
BT - LATIN 2014
PB - Springer-Verlag
T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014
Y2 - 31 March 2014 through 4 April 2014
ER -