The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

Jelínek, Vít and Jelínková, Eva and Kratochvíl, Jan and Tesar, Marek and Vyskocil, Tomás (2010) The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 304-315(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_29).

Full text not available from this repository.

Abstract

It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ. We show that the planar slope number of every series-parallel graph of maximum degree three is three. We also show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is c at most 2O(Δ) . In particular, we answer the question of Dujmovi´ et al. [Computational Geometry 38 (3), pp. 194–212 (2007)] whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f (Δ) slopes. Keywords: graph drawing; planar graphs; slopes; planar slope number.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_29
Classifications: P Styles > P.720 Straight-line
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1090

Actions (login required)

View Item View Item