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, Chicago, IL, USA , 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
ID Code:1090

Repository Staff Only: item control page

References

Barat, J., Matousek, J., Wood, D.R.: Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness. The Electronic Journal of Combinatorics 13, R3 (2006)

Dujmović, V., Suderman, M., Wood, D.R.: Really straight graph drawings. In: c Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 122–132. Springer, Heidelberg (2005)

Dujmović, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Comc putational Geometry 38(3), 181–193 (2007)

Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs c with few slopes and segments. Comp. Geom.-Theor. Appl. 38(3), 194–212 (2007)

Fáry, I.: On straight-line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)

Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Drawing cubic graphs with at most five slopes. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 114–125. Springer, Heidelberg (2007)

Kratochvíl J., Thomas, R.: A note on planar partial 3-trees (in preparation)

Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Computational Geometry: Theory and Applications 42(9), 842–851 (2009)

Pach, J., Pálvölgyi, D.: Bounded-degree graphs can have arbitrarily large slope a o numbers. Electr. J. Combin. 13(1), N1 (2006)

Wade, G.A., Chu, J.-H.: Drawability of complete graphs using a minimal slope set. Comput. J. 37, 139–142 (1994)