Veröffentlichung

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₂-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₁-layout. On the negative side, we demonstrate an infinite family of biconnected 4-planar graphs that require exponential area for an SC₁-layout. Finally, we present an infinite family of biconnected 4-planar graphs that do not admit an SC₁-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} }