How to draw the minimum cuts of a planar graph

Publikationstyp: Zeitschriftenartikel
URI (zitierfähiger Link): http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-71865
Autor/innen: Brandes, Ulrik; Cornelsen, Sabine; Fieß, Christian; Wagner, Dorothea
Erscheinungsjahr: 2004
Erschienen in: Computational Geometry: Theory and Applications ; 29 (2004), 2. - S. 117-133
DOI (zitierfähiger Link): https://dx.doi.org/10.1016/j.comgeo.2004.01.008
Zusammenfassung:
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.
Fachgebiet (DDC): 004 Informatik
Schlagwörter: graph drawing, planar graphs, minimum cuts, cactus representation, clustered graphs
Link zur Lizenz: Deposit-Lizenz
Universitätsbibliographie: Ja

Zitieren

Dateien zu dieser Ressource

[PDF]
Name: cuts.pdf
Größe: 373.4Kb
Format: PDF
Öffnen
Prüfsumme: 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

@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:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" 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> <dc:contributor>Fieß, Christian</dc:contributor> <dc:creator>Fieß, Christian</dc:creator> <dc:creator>Brandes, Ulrik</dc:creator> <dc:creator>Cornelsen, Sabine</dc:creator> <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> <dc:contributor>Brandes, Ulrik</dc:contributor> <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:creator>Wagner, Dorothea</dc:creator> <dc:contributor>Wagner, Dorothea</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:20Z</dc:date> <dc:format>application/pdf</dc:format> <dcterms:issued>2004</dcterms:issued> <dc:language>eng</dc:language> <dc:rights>deposit-license</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"/> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

cuts.pdf 87

Das Dokument erscheint in:

deposit-license Solange nicht anders angezeigt, wird die Lizenz wie folgt beschrieben: deposit-license

KOPS Suche


Stöbern

Mein Benutzerkonto