How to draw the minimum cuts of a planar graph

Brandes, Ulrik; Cornelsen, Sabine; Fieß, Christian; Wagner, Dorothea

doi:10.1016/j.comgeo.2004.01.008

How to draw the minimum cuts of a planar graph

Type of Publication:	Journal article
URI (citable link):	http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-71865
Author:	Brandes, Ulrik; Cornelsen, Sabine; Fieß, Christian; Wagner, Dorothea
Year of publication:	2004
Published in:	Computational Geometry: Theory and Applications ; 29 (2004), 2. - pp. 117-133
DOI (citable link):	https://dx.doi.org/10.1016/j.comgeo.2004.01.008
Summary:	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. This approach is then extended to drawings in which the two vertex subsets of every minimum cut are separated by a simple closed curve. While both approaches work with any embedding-preserving drawing algorithm, we specifically discuss bend-minimum orthogonal drawings.
Subject (DDC):	004 Computer Science
Keywords:	graph drawing, planar graphs, minimum cuts, cactus representation, clustered graphs
Link to License:	Terms of use
Bibliography of Konstanz:	Yes

Cite This

Files in this item

Name: cuts.pdf

Size: 373.4Kb

Format: PDF

View/Open

Checksum: MD5:20c8970dff0296d4839ceaa624b71b90

BRANDES, Ulrik, Sabine CORNELSEN, Christian FIESS, Dorothea WAGNER, 2004. How to draw the minimum cuts of a planar graph. In: Computational Geometry: Theory and Applications. 29(2), pp. 117-133. Available under: doi: 10.1016/j.comgeo.2004.01.008

@article{Brandes2004minim-5683, title={How to draw the minimum cuts of a planar graph}, year={2004}, doi={10.1016/j.comgeo.2004.01.008}, number={2}, volume={29}, journal={Computational Geometry: Theory and Applications}, pages={117--133}, author={Brandes, Ulrik and Cornelsen, Sabine and Fieß, Christian and Wagner, Dorothea} }

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/5683"> <dcterms:bibliographicCitation>First publ. in: Computational Geometry: Theory and Applications 29 (2004), 2, pp. 117-133</dcterms:bibliographicCitation> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5683/1/cuts.pdf"/> <dc:contributor>Fieß, Christian</dc:contributor> <dc:creator>Fieß, Christian</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Brandes, Ulrik</dc:creator> <dc:creator>Cornelsen, Sabine</dc:creator> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5683/1/cuts.pdf"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:20Z</dcterms:available> <dcterms:title>How to draw the minimum cuts of a planar graph</dcterms:title> <dc:contributor>Cornelsen, Sabine</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Brandes, Ulrik</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:20Z</dc:date> <dc:contributor>Wagner, Dorothea</dc:contributor> <dc:creator>Wagner, Dorothea</dc:creator> <dcterms:abstract xml:lang="eng">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. This approach is then extended to drawings in which the two vertex subsets of every minimum cut are separated by a simple closed curve. While both approaches work with any embedding-preserving drawing algorithm, we specifically discuss bend-minimum orthogonal drawings.</dcterms:abstract> <dc:format>application/pdf</dc:format> <dcterms:issued>2004</dcterms:issued> <dc:language>eng</dc:language> <dc:rights>terms-of-use</dc:rights> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5683"/> <dcterms:rights rdf:resource="https://creativecommons.org/licenses/by-nc-nd/2.0/legalcode"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> </rdf:Description> </rdf:RDF>