Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs

Biedl, Therese (2010) Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 280-291 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_27).

Full text not available from this repository.

Abstract

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n2 ) is the established upper and lower bound on the worst-case area. It is a long-standing open problem for what graphs smaller area can be achieved, with results known only for trees and outer-planar graphs. We show here that series-parallel can be drawn in O(n3/2 ) area, but 2-outer-planar graphs and planar graphs of proper pathwidth 3 require Ω(n2 ) area.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_27
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
ID Code:1069

Repository Staff Only: item control page

References

Bertolazzi, P., Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G.: How to draw a series-parallel digraph. Intl. J. Comput. Geom. Appl. 4, 385–402 (1994)

Biedl, T.: New lower bounds for orthogonal graph drawings. Journal of Graph Algorithms and Applications 2(7), 1–31 (1998)

Biedl, T.: Drawing outer-planar graphs in O(n log n) area. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 54–65. Springer, Heidelberg (2002)

Bodlaender, H.: Treewidth: algorithmic techniques and results. In: Privara, I., Ruˇiˇka, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg zc (1997)

Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 515–539. Springer, Heidelberg (2004)

Cohen, R., Di Battista, G., Tamassia, R., Tollis, I.: Dynamic graph drawings: Trees, series-parallel digraphs, and planar st-digraphs. SIAM J. Comput. 24(5), 970–1001 (1995)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.: Graph Drawing: Algorithms for Geometric Representations of Graphs. Prentice-Hall, Englewood Cliffs (1998)

Di Battista, G., Frati, F.: Small area drawings of outerplanar graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 89–100. Springer, Heidelberg (2006)

Dujmovic, V., Fellows, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.: On the parameterized complexity of layered graph drawing. Algorithmica 52, 267–292 (2008)

Dujmovic, V., Morin, P., Wood, D.K.: Layout of graphs with bounded tree-width. SIAM J. on Computing 34(3), 553–579 (2005)

Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Applications 7(4), 335–362 (2003)

Frati, F.: Straight-line drawings of outerplanar graphs in o(dn log n) area. In: Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 225–228 (2007)

Frati, F.: A lower bound on the area requirements of series-parallel graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 159–170. Springer, Heidelberg (2008)

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fary embeddings of planar graphs. In: Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433 (1988)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

Hong, S.H., Eades, P., Quigley, A., Lee, S.H.: Drawing algorithms for series-parallel digraphs in two and three dimensions. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 198–209. Springer, Heidelberg (1999)

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996) 18. Leiserson, C.: Area-efficient graph layouts (for VLSI). In: 21st IEEE Symposium on Foundations of Computer Science, pp. 270–281 (1980)

Miura, K., Nishizeki, T., Nakano, S.: Grid drawings of 4-connected plane graphs. Discrete Computational Geometry 26, 73–87 (2001)

Schnyder, W.: Embedding planar graphs on the grid. In: 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138–148 (1990)

Tamassia, R., Tollis, I.: A unified approach to visibility representations of planar graphs. Discrete Computational Geometry 1, 321–341 (1986)

Tayu, S., Nomura, K., Ueno, S.: On the two-dimensional orthogonal drawing of series-parallel graphs. Discr. Appl. Mathematics 157(8), 1885–1895 (2009)

Wismath, S.: Characterizing bar line-of-sight graphs. In: 1st ACM Symposium on Computational Geometry, Baltimore, Maryland, USA, pp. 147–152 (1985)