Smooth Orthogonal Drawings of Planar Graphs

DOI10.1007/978-3-642-54423-1_13MaRDI QIDQ5405035zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(12)

• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• An annotated review on graph drawing and its applications
• Discrete optimization methods for group model selection in compressed sensing
• Linear-time rectilinear drawings of subdivisions of triconnected cubic planar graphs with orthogonally convex faces
• Orthogonal drawings based on the stratification of planar graphs
• Smooth orthogonal layouts
• Smooth orthogonal layouts
• scientific article; zbMATH DE number 2165566 (Why is no real title available?)
• Lombardi drawings of knots and links
• Obedient plane drawings for disk intersection graphs
• Orthogonal Drawings of Plane Graphs Without Bends
• 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)