Confluent Layered Drawings

Eppstein, David and Goodrich, Michael T. and Meng, Jeremy Yu (2004) Confluent Layered Drawings. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 184-194 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_20).

Full text not available from this repository.

Abstract

We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of graphs from the mixed style drawings. The basic idea is to cover a layered graph by complete bipartite subgraphs (bicliques), then replace bicliques with tree-like structures. The biclique cover problem is reduced to a special edge coloring problem and solved by heuristic coloring algorithms. Our method can be extended to obtain multi-depth confluent layered drawings. Work by the first author is supported by NSF grant CCR-9912338. Work by the second and the third author is supported by NSF grants CCR-0098068, CCR-0225642, and DUE-0231467.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_20
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
P Styles > P.300 Curved
ID Code:586

Repository Staff Only: item control page

References

W. Barth, M. Jünger, and P. Mutzel. Simple and efficient bilayer crossing counting. In M. Goodrich and S. Kobourov, editors, Ghraph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Computer Science, pages 130-141. Springer-Verlag, 2002.

Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251-256, 1979.

G. Campers, O. Henkes, and J. P. Leclerq. Graph coloring heuristics: A survey, some new propositions and computational experiences on random and "Leighton's" graphs. In G. K. Rand, editor, Operational research '87 (Buenos Aires, 1987), pages 917-932. North-Holland Publishing Co, 1988.

M. J. Carpano. Automatic display of hierarchized graphs for computer aided decisions analysis. IEEE Trans. Syst. Man Cybern., SMC-10(11):705-715, 1980.

M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Y. Meng. Confluent drawing: Visualizing nonplanar diagrams in a planar way. In G. Liotta, editor, Graph Drawing (Proc. GD '03), volume 2912 of Lecture Notes Comput. Sci., pages 1-12. Springer-Verlag, 2003.

P. Eades and K. Sugiyama. How to draw a directed graph. J. Inform. Process., 13:424-437, 1991.

J. Ellson, E. Gansner, E. Koutsofios, and S. North. Graphviz. URL:http://www. research.att.com/sw/tools/graphviz.

T. Eschbach, W. Günther, R. Drechsler, and B. Becker. Crossing reduction by windows optimization. In M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD '02) volume 2528 of Lecture Notes in Computer Science, pages 285-294. Springer-Verlag, 2002.

P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degree of graphs. Discrete Math., 160:127-148, 1996.

M. Forster. Applying crossing reduction strategies to layered compound graphs. In M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Computer Sci., pages 276-284. Springer-Verlag, 2002.

E. R. Gansner, E. Koutsofios, S. C. North, and K. P. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19:214-230, 1993.

E. R. Gansner, S. C. North, and K. P. Vo. DAG - A program that draws directed graphs. Softw. - Pract. Exp., 18(11):1047-1062, 1988.

M. R. Garey and D. S. Johnson. Computers and Intactability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.

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

D. J. Gschwind and T. P. Murtagh. A recursive algorithm for drawing hierarchical directed graphs. Technical Report CS-89-02, Department of Computer Science, Williams College, 1989.

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

E. Koutsofios and S. North. Drawing graphs with dot. Technical report, At&T http://www.research.bell-labs.com/dist/drawdag.

F. T. Leighton. A graph coloring algorithm for large scheduling problems. Journal of Research of National Bureau of Standard, 84:489-506, 1979.

E. B. Messinger. Automatic layout of large directed graphs. Technical Report 88-07-08, Department of Computer Science, University of Washington, 1988.

E. B. Messinger. L. A. Rowe, and R. H. Henry. A divide-and-conquer algorithm for the automatic layout of large directed graphs. IEEE Trans. Syst. Man Ccybern., SMC-21(1):1-12, 1991.

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

F. Newbery Paulisch and W. F. Tichy. EDGE: An extendible graph editor. Softw. - Pract. Exp., 20(S1):63-88, 1990. also as Technical Report 8/88, Fakultät für Informatik, Univ. of Karlsruhe, 1988.

M. Newton, O. Sykora, and I. Vrt'o. Two new heuristics for two-sided bipartite graph drawing. In M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD '02), volume 2528 of Lecture Notes in Computer Science, pages 312-319. Springer-Verlag, 2002.

H. Purchase. Which aesthetic has the greatest effect on human understanding? In G. Di Battoista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 248-261. Springer-Verlag, 1997.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern., SMC-11(2):109-125, 1981.

V. Waddle and A. Malhotra. An E log E line crossing algorithm for levelled graphs. In J. Kratochvil, editor, Graph Drawing (Proc. GD '99), volume 1731 of Lecture Notes Comput. Sci., pages 59-71. Springer-Verlag, 1999.