Titel: | Smooth Orthogonal Drawings of Planar Graphs |
---|---|
AutorInnen: |
Muhammad Jawaherul Alam
Michael A. Bekos Michael Kaufmann Philipp Kindermann Stephen G. Kobourov Alexander Wolff |
Kategorie: | Konferenzbandbeiträge |
erschienen in: | Proceedings of the 13th Latin American Symposium on Theorectical Informatics (LATIN'14), pp. 144-155 |
Abstract: | 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 SC_{2}-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 SC_{1}-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 SC_{1}-layout. |
Download: | Proceeding Website |
BibTeX-Eintrag: | @InProceedings{abkkkw-sodpg-latin14, Title = {Smooth Orthogonal Drawings of Planar Graphs}, Author = {Muhammad Jawaherul Alam and Michael A. Bekos and Michael Kaufmann and Philipp Kindermann and Stephen G. Kobourov and Alexander Wolff}, Booktitle = {Proceedings of the 13th Latin American Symposium on Theorectical Informatics (LATIN'14)}, Year = {2014}, Editor = {Pardo, A. and Viola, A.}, Pages = {144--155}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {8392}, Abstract = {In \emph{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 \emph{edge complexity}, that is, with few segments per edge. We say that a graph has \emph{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 SC$_2$-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 SC$_1$-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 SC$_1$-layout.}, Doi = {10.1007/978-3-642-54423-1_13} } |