Confluent Drawing Algorithms Using Rectangular Dualization

Quercini, Gianluca and Ancona, Massimo (2011) Confluent Drawing Algorithms Using Rectangular Dualization. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany, , pp. 341-352 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_31).

Full text not available from this repository.

Abstract

The need of effective drawings for non-planar dense graphs is motivated by the wealth of applications in which they occur, including social network analysis, security visualization and web clustering engines, just to name a few. One common issue graph drawings are affected by is the visual clutter due to the high number of (possibly intersecting) edges to display. Confluent drawings address this problem by bundling groups of edges sharing the same path, resulting in a representation with less edges and no edge intersections. In this paper we describe how to create a confluent drawing of a graph from its rectangular dual and we show two important advantages of this approach.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_31
Classifications:P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
ID Code:1219

Repository Staff Only: item control page

References

Angelini, P., Frati, F., Kaufmann, M.: Straight-Line Rectangular Drawings of Clustered Graphs. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 25–36. Springer, Heidelberg (2009)

Biedl, T.C., Kant, G., Kaufmann, M.: On Triangulating Planar Graphs under the Four-Connectivity Constraint. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824, pp. 83–94. Springer, Heidelberg (1994)

Chiba, N., Nishizeki, T.: Arboricity and Subgraph Listing. SIAM Journal on Computing 14(1), 210–223 (1985)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 1–12. Springer, Heidelberg (2004)

Eades, P., Feng, Q.-W., Nagamochi, H.: Draw10.1007/978-3-642-18469-7_31ing Clustered Graphs on an Orthogonal Grid. Journal on Graph Algorithms and Applications 3(4), 3–29 (1999)

Eades, P., Gutwenger, C., Hong, S.-H., Mutzel, P.: Graph Drawing Algorithms. In: Algorithms and Theory of Computation Handbook, 2nd edn., vol. 2, CRC Press, Boca Raton (2009)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta-Confluent Drawings. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 165–176. Springer, Heidelberg (2006)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent Layered Drawings. Algorithmica 47(4), 439–452 (2007)

Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for Clustered Graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995)

Feng, Q.: Algorithms for Drawing Clustered Graphs. Ph.D. thesis, University of Newcastle, Australia (1997)

Fössmeier, U., Kaufmann, M.: Drawing High Degree Graphs with Low Bend Numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 254–266. Springer, Heidelberg (1996)

Garg, A., Tamassia, R.: A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 201–216. Springer, Heidelberg (1997)

He, X.: On Floorplans of Planar Graphs. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 426–435. ACM, New York (1997)

Hirsch, M., Meijer, H., Rappaport, D.: Biclique Edge Cover Graphs and Confluent Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 405–416. Springer, Heidelberg (2007)

Hui, P., Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Train Tracks and Confluent Drawings. Algorithmica 47(4), 465–479 (2007)

Kant, G., He, X.: Two Algorithms for Finding Rectangular Duals of Planar Graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 396–410. Springer, Heidelberg (1994)

Koźmiński, K., Kinnen, E.: Rectangular Duals of Planar Graphs. Networks 15(2), 145–157 (1985)

Lai, Y.-T., Leinwand, S.M.: Algorithms for Floorplan Design via Rectangular Dualization. IEEE Transactions on Computer-Aided Design 7(12), 1278–1289 (1988)

Quercini, G.: Optimizing and Visualizing Planar Graphs via Rectangular Dualization. Ph.D. thesis, University of Genoa, Genoa, Italy (2009)