Publikace na Matematicko-fyzikální fakulta |
2013
Abstrakt
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 D.
We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most O(D^5). In particular, we answer the question of Dujmovic et al. (Comput.
Geom 38(3):194-212, 2007) whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f (D) slopes.