How to draw the minimum cuts of a planar graph
Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können am Montag, 6.2. und Dienstag, 7.2. keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted on Monday, Feb. 6 and Tuesday, Feb. 7.)
| 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: | Attribution-NonCommercial-NoDerivs 2.0 Generic |
| Bibliography of Konstanz: | Yes |
Cite This
Files in this item
![[PDF]](/themes/Kops/images/mimes/pdf.png "PDF file"){kind=small}
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> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <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> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5683"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> </rdf:Description> </rdf:RDF>
Downloads since Oct 1, 2014 (Information about access statistics)
| cuts.pdf | 372 |
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 2.0 Generic
Search KOPS
Browse
My Account
