Drawing Outer 1-planar Graphs with Few Slopes

Di Giacomo, Emilio and Liotta, Giuseppe and Montecchiani, Fabrizio (2014) Drawing Outer 1-planar Graphs with Few Slopes. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 174-185(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_15).

Full text not available from this repository.


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 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 extends a previous result by Knauer et al. about the planar slope number of outerplanar graphs (CGTA, 2014). We also show that O(Δ2) 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(Δ5) and is proved by Jelínek et al. (Graphs and Combinatorics, 2013).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_15
Classifications: D Aesthetics > D.999 Others
G Algorithms and Complexity > G.420 Crossings
M Methods > M.900 Tree
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1431

Actions (login required)

View Item View Item