Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way

Dickerson, Matthew and Eppstein, David and Goodrich, Michael T. and Meng, Jeremy Yu (2004) Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 1-12 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_1).

Full text not available from this repository.

Abstract

We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a crossing-free manner, graph - such as software interaction diagrams - that would normally have many crossings. The main idea of this approach is quite simple: we allow groups of edges to be merged together and drawn as "tracks" (similar to train tracks). Producing such confluent diagrams automatically from a graph with many crossings is quite challenging, however, so we offer two heuristic algorithms to test if a non-planar graph can be drawn efficiently in a confluent way. In addition, we identify several large classes of graphs that can be completely categorized as being either confluently drawable or confluently non-drawable.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_1
Classifications:M Methods > M.700 Planarization-based
P Styles > P.540 Planar
ID Code:406

Repository Staff Only: item control page

References

T. Ball and S. G. Eick. Software visualization in the large. IEEE Computer, 29(4):33-43, 1996.

C. Batini, E. Nardelli, and R. Tamassia. A layout algorithm for data flow diagrams. IEEE Trans. Softw. Eng., SE-12(4):538-546, 1986.

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan, London, 1976.

R. Breu, U. Hinkel, C. Hofmann, C. Klein, B. Paech, B. Rumpe, and V. Thurner. Towards a formalization of the unified modeling language. In Proc. 11th European Conf. Object-Oriented Programming (ECOOP '97), volume 1241 of Lecture Notes in Computer Science, pages 344-366, 1997.

C. Chambers, J. Dean, and D. Grove. A framework for selective recompilation in the presence of complex intermodule dependencies. In Proceedings: 17th International Conference on Software Engineering, pages 221-230, 1995.

C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. In Proc. Graph Drawing, volume 1731 of Lecture Notes in Computer Science, pages 117-126, 1999.

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14:210-223, 1985.

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci., 30(1):54-76, 1985.

M. Chrobak and T. H. Payne. A linear time algorithm for drawing a planar graph on a grid. Technical Report UCR-CS-90-2, Dept. of Math. and Comput. Sci., Univ. California Riverside, 1990.

D. G. Corneil, H. Lerchs, and L. S. Burlingham. Complement reducible graphs. Discrete Appl. Math., 3:163-174, 1981.

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

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

P. Eades and P. Mutzel. Graph drawing algorithms. In M. Atallah, editor, CRC Handbook of Algorithms and Theory of Computation, chapter 9. CRC Press, 1999.

D. Eppstein. Arboricity and bipartite subgraph listing algorithms. Information Processing Letters, 51(4):207-211, August 1994.

T. Feder, A. Meyerson, R. Motwani, L. O'Callaghan, and R. Panigrahy. Representing graph metrics with fewest edges. In Proceedings: 20th Annual Symposium on Theoretical Aspects of Computer Science, volume 2607 of Lecture Notes Comput. Sci., pages 355-366, 2003.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete, SIAM J. Algebraic and Discrete Methods, 4(3):312-316, 1983.

D. Grove, G. DeFouw, J. Dean, and C. Chambers. Call graph construction in object-oriented languages. In Proc. of ACM Symp. on Object-Oriented Prog. Sys., Lang. and Applications (OOPSLA), pages 108-124, 1997.

P. Haynes, T. J. Menzies, and R. F. Cohen. Visualisations of large object-oriented systems. In P. D. Eades and K. Zhang, editors, Software Visualisation, volume 7, pages 205-218. World Scientific, Singapore, 1996.

M. Jünger, E. K. Lee, P. Mutzel, and T. Odenthal. A polyhedral approach to the multi-layer crossing minimization problem. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 13-24. Springer-Verlag, 1997.

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl., 1(1):1-25, 1997.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

M. Kaufmann and D. Wagner. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

D. E. Knuth. Computer drawn flowcharts. Commun. ACM, 6, 1963.

X. Lin. On the computational complexity of edge concentration. DAMATH: Discrete Applied Mathematics and Combinatorial Operational Research, 101, 2000.

P. Mutzel. An alternative method to crossing minimization on hierarchical graphs. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 318-333. Springer-Verlag, 1997.

P. Mutzel and T. Zeigler. The constrained crossing minimization problem. In J. Kratochvíl, editor, Graph Drawing Conference, volume 1731 of Lecture Notes in Computer Science, pages 175-185. Springer-Verlag, 1999.

F. J. Newbery. Edge concentration: A method for clustering directed graphs. In Proc. 2nd Internat. Workshop on Software Configuration Management, pages 76-85, 1989.

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms, volume 32 of Ann. Discrete Math. North-Holland, Amsterdam, The Netherlands, 1988.

R. C. Penner and J. L. Harer. Combinatorics of Train Tracks, volume 125 of Annals of Mathematics Studies. Princeton Univ. Press, Princeton, NJ, 1992.

B. Price, R. Baecker, and I. Small. A principled taxonomy of software visualization. Journal of Visual Languages and Computing, 4(3):211-266, 1993.

H. Purchase. Which aesthetic has the greatest effect on human understanding? In G. Di Battista, editor, Proc. 5th Int. Symp. Graph Drawing, GD, number 1353 in Lecture Notes in Computer Science, LNCS, pages 248-261. Springer-Verlag, 18-20 Sept. 1997.

G.-C. Roman and K. C. Cox. A taxonomy of program visualization systems. IEEE Computer, 26(12):11-24, 1993.

J. Rumbaugh, I. Jacobson, and G. Booch. The Unified Modeling Language Reference Manual. Addison-Wesley, 1998.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.

J. T. Stasko and E. Kraemer. A methodology for building application-specific visualizations of parallel programs. Journal of Parallel and Distributed Computing, 18(2):258-264, 1993.

R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

F. Tip and J. Palsberg. Scalable propagation-based call graph construction algorithms. ACM SIGPLAN Notices, 35(10):281-293, 2000.