Planar and Plane Slope Number of Partial 2-Trees

Lenhart, William J. and Liotta, Giuseppe and Mondal, Debajyoti and Nishat, Rahnuma Islam (2013) Planar and Plane Slope Number of Partial 2-Trees. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 412-423 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_36).

Full text not available from this repository.

Abstract

We prove tight bounds (up to a small multiplicative or additive constant) for the plane and the planar slope numbers of partial 2-trees of bounded degree. As a byproduct of our techniques, we answer a long standing question by Garg and Tamassia about the angular resolution of the planar straight-line drawings of series-parallel graphs of bounded degree.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
P Styles > P.720 Straight-line
ID Code:1393

Repository Staff Only: item control page

References

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice- Hall, Englewood Cliffs (1999)

Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Computational Geometry 38(3), 194–212 (2007)

Garg, A., Tamassia, R.: Planar drawings and angular resolution: Algorithms and bounds. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 12–23. Springer, Heidelberg (1994)

Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesar, M., Vyskocil, T.: The planar slope number of planar partial 3-trees of bounded degree. Graphs and Combinatorics 29(4), 981–1005 (2013)

Kant, G.: Hexagonal grid drawings. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 263–276. Springer, Heidelberg (1993)

Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM J. Discrete Math. 27(2), 1171–1183 (2013)

Knauer, K., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 323–334. Springer, Heidelberg (2012)

Mondal, D., Nishat, R.I., Biswas, S., Rahman, M.S.: Minimum-segment convex drawings of 3-connected cubic plane graphs. Journal of Combinatorial Optimization 25(3), 460–480 (2013)

Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 254–265. Springer, Heidelberg (2011)

Papakostas, A., Tollis, I.G.: Improved algorithms and bounds for orthogonal drawings. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 40–51. Springer, Heidelberg (1995)