The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
| Autor: | Jelínek, Vít, Jelínková, Eva, Kratochvíl, Jan, Lidický, Bernard, Tesař, Marek, Vyskočil, Tomš |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00373-012-1157-z |
| Popis: | 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 $\Delta$. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O(\Delta^5)$. In particular, we answer the question of Dujmovi\'c 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(\Delta)$ slopes. Comment: 34 pages, 18 figures, old version was at Graph Drawing 2009 |
| Databáze: | arXiv |
| Externí odkaz: |
|