Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity

摘要

While orthogonal drawings have a long history, smooth orthogonal drawings have been introduced only recently. So far, only planar drawings or drawings with an arbitrary number of crossings per edge have been studied. Recently, a lot of research effort in graph drawing has been directed towards the study of beyond-planar graphs such as 1-planar graphs, which admit a drawing where each edge is crossed at most once. In this paper, we consider graphs with a fixed embedding. For 1-planar graphs, we present algorithms that yield orthogonal drawings with optimal curve complexity and smooth orthogonal drawings with small curve complexity. For the subclass of outer-l-planar graphs, which can be drawn such that all vertices lie on the outer face, we achieve optimal curve complexity for both, orthogonal and smooth orthogonal drawings.