Small-Area Orthogonal Drawings of 3-Connected Graphs

Biedl, Therese and Schmidt, Jens M. (2015) Small-Area Orthogonal Drawings of 3-Connected Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 153-165 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_13).

Full text not available from this repository.

Abstract

It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most (49/64)*n^2+O(n)≈0.76n^2. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to (9/16)*n^2+O(n)≈0.56n^2. The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.280 Canonical Ordering
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:1485

Repository Staff Only: item control page

References

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)

Cheriyan, J., Maheshwari, S.N.: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms 9(4), 507–537 (1988)

Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comput. 34(4), 924–945 (2005)

de Fraysseix, H., de Mendez, P.O.: Regular orientations, arboricity and augmentation. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 111–118. Springer, Heidelberg (1995)

Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: 19th Annual ACM Symposium on Theory of Computing, pp. 365–372 (1987)

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

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

Mondshein, L.F.: Combinatorial ordering and the geometric embedding of graphs. Ph.D. thesis, M.I.T. Lincoln Laboratory / Harvard University (1971)

Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1–2), 83–110 (1998)

Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientation of planar graphs. Discrete Comput. Geom. 1, 343–353 (1986)

Schäffter, M.: Drawing graphs on rectangular grids. Discrete Appl. Math. 63, 75–89 (1995)

Schmidt, J.M.: The Mondshein sequence (2013). http://​arxiv.​org/​pdf/​1311.​0750.​pdf

Schmidt, J.M.: The Mondshein sequence. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 967–978. Springer, Heidelberg (2014)

Biedl, T.: Optimal orthogonal drawings of triconnected plane graphs. In: McCune, W., Padmanabhan, R. (eds.) Automated Deduction in Equational Logic and Cubic Curves. LNCS, vol. 1095, pp. 333–344. Springer, Heidelberg (1996)

Tamassia, R., Tollis, I.: A unified approach to visibility representations of planargraphs. Discrete Comput. Geom. 1, 321–341 (1986)

Tamassia, R., Tollis, I.G., Vitter, J.S.: Lower bounds for planar orthogonal drawings of graphs. Inf. Process. Lett. 39, 35–40 (1991)

Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. C–30(2), 135–140 (1981)