Biclique Edge Cover Graphs and Confluent Drawings

Hirsch, Michael and Meijer, Henk and Rappaport, David (2007) Biclique Edge Cover Graphs and Confluent Drawings. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 405-416 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_39).

Full text not available from this repository.

Abstract

Confluent drawing is a technique that allows some non-planar graphs to be visualized in a planar way. This approach merges edges together, drawing groups of them as single tracks, similar to train tracks. In the general case, producing confluent drawings automatically has proven quite difficult. We introduce the biclique edge cover graph that represents a graph G as an interconnected set of cliques and bicliques. We do this in such a way as to permit a straightforward transformation to a confluent drawing of G. Our result is a new sufficient condition for confluent planarity and an additional algorithmic approach for generating confluent drawings. We give some experimental results gauging the performance of existing confluent drawing heuristics.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_39
Classifications:P Styles > P.540 Planar
P Styles > P.300 Curved
ID Code:796

Repository Staff Only: item control page

References

Devine, J.: Confluent graphs. Master's thesis, Queen's University (2005).

Hui, P., Schaefer, M., Stefankovic, D.: Train tracks and confluent drawings. In Pach, J., ed.: Proc. 12th Int. Symp. Graph Drawing (GD 2004). Number 3383 in Lecture Notes in Computer Science, Springer-Verlag (2004) 318-328.

Newbery, F.J.: Edge concentration: a method for clustering directed graphs. In: Proc. 2nd Int.Works. on Soft. conguration management, ACM Press (1989) 76-85.

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. In Pach, J., ed.: Proc. 12th Int. Symp. Graph Drawing (GD 2004). Number 3383 in Lecture

Notes in Computer Science, Springer-Verlag (2004) 184-194.

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta-confluent drawings. In Healy, P., Nikolov, N.S., eds.: Proc. 13th Int. Symp. Graph Drawing (GD 2005). Number 3843 in Lecture Notes in Computer Science, Springer-Verlag (2006) 165-176.

Dickerson, M.T., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: visualizing non-planar diagrams in a planar way. In: Proc. 11th Int. Symp. Graph Drawing (GD 2003). Lecture Notes in Computer Science, Springer-Verlag (2003).

Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. In: SIAM Journal on Computing. Volume 6. (1977) 505-517.

Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discrete Applied Mathematics 145(1) (2004) 11-21.

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

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

Hirsch, M.: Generating confluent drawings: Theory and practice. Master's thesis, Queen's University (2006).

Di Battista, G., Garg, A., Liotta, G.: An experimental comparison of three graph drawing algorithms (extended abstract). In: Proc. 11th Annual Symp. Computational Geometry (SCG '95), New York, NY, USA, ACM Press (1995) 306-315.

Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Softw. Pract. Exper. 30(11) (2000) 1203-1233.

Barghouti, N.S., Mocenigo, J., Lee, W.: Grappa: A graph package in java. In Di Battista, G., ed.: Proc. 5th Int. Symp. Graph Drawing (GD '97). Volume 1353 of

Lecture Notes in Computer Science., Springer (1997) 336-343.

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, NJ, USA (1998).