Drawing Outer 1-planar Graphs with Few Slopes

Abstract

A graph is outer 1-planar if it admits a drawing where each vertex is on the outer face and each edge is crossed by at most another edge. Outer 1-planar graphs are a superclass of the outerplanar graphs and a subclass of the planar partial 3-trees. We show that an outer 1-planar graph G of bounded degree ∆ admits an outer 1-planar straight-line drawing that uses O(∆) different slopes, which generalizes a previous result by Knauer et al. about the outerplanar slope number of outerplanar graphs (Knauer, Micek, and Walczak. CGTA, 2014). We also show that O(∆²) slopes suffice to construct a crossing-free straight-line drawing of G; the best known upper bound on the planar slope number of planar partial 3-trees of bounded degree ∆ is O(∆⁵) as proved by Jelínek et al. (V. Jelínek, E. Jelínková, J. Kratochvíl, B. Lidický, M. Tesar, and T. Vyskocil. Graphs and Combinatorics, 2013).