Smooth Orthogonal Drawings of Planar Graphs

DOI10.1007/978-3-642-54423-1_13zbMATH Open1405.68232arXiv1312.3538OpenAlexW1533187596MaRDI QIDQ5405035FDOQ5405035

Authors: Md. Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Alexander Wolff 

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1312.3538

Recommendations

• scientific article; zbMATH DE number 1974134
• Orthogonal drawings based on the stratification of planar graphs
• Orthogonal drawings based on the stratification of planar graphs
• On orthogonally convex drawings of plane graphs
• scientific article; zbMATH DE number 2084292
• Orthogonal Drawings of Plane Graphs Without Bends
• Computing and Combinatorics
• Orthogonal Drawings for Plane Graphs with Specified Face Areas
• Morphing orthogonal planar graph drawings
• Techniques for the Refinement of Orthogonal Graph Drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (13)

• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings
• An annotated review on graph drawing and its applications
• Lombardi Drawings of Knots and Links
• Discrete optimization methods for group model selection in compressed sensing
• Orthogonal drawings based on the stratification of planar graphs
• Smooth orthogonal layouts
• Smooth orthogonal layouts
• Title not available (Why is that?)
• Obedient plane drawings for disk intersection graphs
• Orthogonal Drawings of Plane Graphs Without Bends
• Title not available (Why is that?)
• Orthogonal Drawings for Plane Graphs with Specified Face Areas

This page was built for publication: Smooth Orthogonal Drawings of Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405035)