How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract)

Brandes, Ulrik and Cornelsen, Sabine and Wagner, Dorothea (2001) How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 103-114 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_10).

Full text not available from this repository.

Abstract

We show how to utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a first approach the cactus is transformed into a hierarchical clustering of the graph that contains complete information on all the minimum cuts. We present an algorithm for c-planar orthogonal drawings of hierarchically clustered planar graphs with rectangularly shaped cluster boundaries and the minimum number of bends. This approach is then extended to drawings in which the two vertex subsets of every minimum cut are separated by a simple closed curve.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_10
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.180 Cluster
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.350 Clusters
P Styles > P.540 Planar
ID Code:308

Repository Staff Only: item control page

References

Y. Dinitz, A. V. Karzanov, and M. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. In A. Fridman, editor, Studies in Discrete Optimization, pages 290-306. Nauka, 1976. (in Russian).

Y. Dinitz and Z. Nutov. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in graph and its incremental maintenance. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC '95), pages 509-518. ACM, The Association for Computing Machinery, 1995.

P. Eades, Q. Feng, and H. Nagamochi. Drawing clustered graphs on an orthogonal grid. Journal on Graph Algorithms and Applications, 3(4):3-29, 1999.

Q. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Proceedings of the 3rd European Symposium on Algorithms (ESA '95), volume 979 of Lecture Notes in Computer Science, pages 213-226. Springer, 1995.

L. Fleischer. Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time. Journal of Algorithms, 33(1):51-72, 1999.

A. Garg and R. Tamassia. A new minimum cost flow algorithm with applications to graph drawing. In S. C. North, editor Proceedings of the 4th International Symposium on Graph Drawing (GD '96), volume 1190 of Lecture Notes in Computer Science, pages 201-213. Springer, 1996.

M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Fatser shortest-path algorithms for planar garphs. Journal of Computer and System Sciences, 55:3-23, 1997. Special Issue on Selected Papers from STOC 1994.

G. W. KLau and P. Mutzel. Quasi orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-031, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998.

D. Lütke-Hüttmann. Knickminimales Zeichnen 4-planarer Clustergraphen. Master's thesis, Universität des Saarlandes, 1999. (Diplomarbeit).

K. Mehlhorn and S. Näher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. Project home pages at http://www.mpi-sb.mpg.de/LEDA/.

P. Mutzel, C. Gutwenger, R. Brockenauer, S. Fialko, G. W. Klau, M. Krüger, T. Ziegler, S. Näher, D. Alberts, D. Ambras, G. Koch, M. Jünger, C. Buchheim, and S. Leipert. A library of algorithms for graph drawing. In S. H. Whitesides editor, Proceedings of the 6th International Symposium on Graph Drawing (GD'98), volume 1547 of Lecture Notes in Computer Science, pages 456-457. Springer, 1998. Project home page at http://www.mpi-sb.mpg.de/AGD/.

H. Nagamochi and T. Kameda. Constructing cactus representation for all minimum cuts in an undirected network. Journal of the Operations Research, 39(2):135-158, 1996.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16:421-444, 1987.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, , 18(1):61-79, 1988.