Publikation: How to draw the minimum cuts of a planar graph
Lade...
Dateien
Datum
2004
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Computational Geometry: Theory and Applications. 2004, 29(2), pp. 117-133. Available under: doi: 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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
graph drawing, planar graphs, minimum cuts, cactus representation, clustered graphs
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
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. 2004, 29(2), pp. 117-133. Available under: doi: 10.1016/j.comgeo.2004.01.008BibTex
@article{Brandes2004minim-5683, year={2004}, doi={10.1016/j.comgeo.2004.01.008}, title={How to draw the minimum cuts of a planar graph}, 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: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/server/rdf/resource/123456789/5683"> <dc:format>application/pdf</dc:format> <dc:contributor>Cornelsen, Sabine</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Brandes, Ulrik</dc:contributor> <dc:contributor>Fieß, Christian</dc:contributor> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5683/1/cuts.pdf"/> <dc:creator>Fieß, Christian</dc:creator> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5683/1/cuts.pdf"/> <dc:creator>Wagner, Dorothea</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5683"/> <dc:creator>Cornelsen, Sabine</dc:creator> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dcterms:title>How to draw the minimum cuts of a planar graph</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:bibliographicCitation>First publ. in: Computational Geometry: Theory and Applications 29 (2004), 2, pp. 117-133</dcterms:bibliographicCitation> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:20Z</dc:date> <dcterms:issued>2004</dcterms:issued> <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> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:59:20Z</dcterms:available> <dc:contributor>Wagner, Dorothea</dc:contributor> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dc:creator>Brandes, Ulrik</dc:creator> </rdf:Description> </rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja