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 , pp. 103-114(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item