@kindermann

Smooth Orthogonal Drawings of Planar Graphs

, , , , , and . Proc. 11th Latin American Sympos. on Theoretical Informatics (LATIN'14), volume 8392 of Lecture Notes in Computer Science, page 144--155. Springer-Verlag, (April 2014)
DOI: 10.1007/978-3-642-54423-1_13

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. 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.

Links and resources

Tags

community

  • @kindermann
  • @awolff
  • @dblp
@kindermann's tags highlighted