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. Further, we show that every
biconnected 4-outerplane graph admits an SC_1-layout. On the negative
side, we demonstrate a family of biconnected 4-planar graphs that
requires exponential area for an SC_1-layout. Finally, we present an
infinite family of biconnected 4-planar graphs that does
not admit an SC_1-layout.
%0 Conference Paper
%1 abkkkw-sodpg-latin14
%A Alam, Md. Jawaherul
%A Bekos, Michael A.
%A Kaufmann, Michael
%A Kindermann, Philipp
%A Kobourov, Stephen G.
%A Wolff, Alexander
%B Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN'14)
%D 2014
%E Pardo, A.
%E Viola, A.
%I Springer-Verlag
%K myown
%P 144--155
%R 10.1007/978-3-642-54423-1_13
%T Smooth Orthogonal Drawings of Planar Graphs
%V 8392
%X 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. Further, we show that every
biconnected 4-outerplane graph admits an SC_1-layout. On the negative
side, we demonstrate a family of biconnected 4-planar graphs that
requires exponential area for an SC_1-layout. Finally, we present an
infinite family of biconnected 4-planar graphs that does
not admit an SC_1-layout.
@inproceedings{abkkkw-sodpg-latin14,
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. Further, we show that every
biconnected 4-outerplane graph admits an SC_1-layout. On the negative
side, we demonstrate a family of biconnected 4-planar graphs that
requires exponential area for an SC_1-layout. Finally, we present an
infinite family of biconnected 4-planar graphs that does
not admit an SC_1-layout.},
added-at = {2013-07-19T17:53:52.000+0200},
arxiv = {https://arxiv.org/abs/1312.3538},
author = {Alam, Md. Jawaherul and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Kobourov, Stephen G. and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2cba6877a34667698be0a751aebaaa290/kindermann},
booktitle = {Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN'14)},
doi = {10.1007/978-3-642-54423-1_13},
editor = {Pardo, A. and Viola, A.},
interhash = {981803b99fe31563d0b631362bb91f20},
intrahash = {cba6877a34667698be0a751aebaaa290},
keywords = {myown},
month = apr,
pages = {144--155},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2014-latin-smooth.pdf},
timestamp = {2018-09-18T06:19:30.000+0200},
title = {Smooth Orthogonal Drawings of Planar Graphs},
volume = 8392,
year = 2014
}