How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract)

Kurzanzeige
dc.contributor.authorBrandes, Ulrik
dc.contributor.authorCornelsen, Sabine
dc.contributor.authorWagner, Dorotheadeu
dc.date.accessioned2011-03-24T16:00:38Zdeu
dc.date.available2011-03-24T16:00:38Zdeu
dc.date.issued2002-05-27
dc.description.abstractWe show how 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.eng
dc.description.versionpublished
dc.format.mimetypeapplication/pdfdeu
dc.identifier.citationFirst publ. in: Proceedings of the 8th International Symposium on Graph Drawing (GD 2000) (LNCS 1984), 2001, pp. 103-114deu
dc.identifier.doi10.1007/3-540-44541-2_10
dc.identifier.ppn302438688deu
dc.identifier.urihttp://kops.uni-konstanz.de/handle/123456789/5845
dc.language.isoengdeu
dc.legacy.dateIssued2009deu
dc.rightsAttribution-NonCommercial-NoDerivs 2.0 Generic
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.0/
dc.subject.ddc004deu
dc.titleHow to Draw the Minimum Cuts of a Planar Graph (Extended Abstract)eng
dc.typeINPROCEEDINGSdeu
dspace.entity.typePublication
kops.citation.bibtex
@inproceedings{Brandes2002-05-27Minim-5845,
  year={2002},
  doi={10.1007/3-540-44541-2_10},
  title={How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract)},
  number={1984},
  isbn={978-3-540-41554-1},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Graph Drawing},
  pages={103--114},
  editor={Marks, Joe},
  author={Brandes, Ulrik and Cornelsen, Sabine and Wagner, Dorothea}
}
kops.citation.iso690BRANDES, Ulrik, Sabine CORNELSEN, Dorothea WAGNER, 2002. How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract). In: MARKS, Joe, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 103-114. Lecture Notes in Computer Science. 1984. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10deu
kops.citation.iso690BRANDES, Ulrik, Sabine CORNELSEN, Dorothea WAGNER, 2002. How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract). In: MARKS, Joe, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 103-114. Lecture Notes in Computer Science. 1984. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10eng
kops.citation.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/5845">
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5845"/>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:38Z</dcterms:available>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">We show how 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.</dcterms:abstract>
    <dcterms:title>How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract)</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:format>application/pdf</dc:format>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:language>eng</dc:language>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5845/1/cactus_clustered.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:38Z</dc:date>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 8th International Symposium on Graph Drawing (GD 2000) (LNCS 1984), 2001, pp. 103-114</dcterms:bibliographicCitation>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:issued>2002-05-27</dcterms:issued>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5845/1/cactus_clustered.pdf"/>
  </rdf:Description>
</rdf:RDF>
kops.description.openAccessopenaccessgreen
kops.flag.knbibliographyfalse
kops.identifier.nbnurn:nbn:de:bsz:352-opus-73461deu
kops.opus.id7346deu
kops.sourcefieldMARKS, Joe, ed.. <i>Graph Drawing</i>. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 103-114. Lecture Notes in Computer Science. 1984. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10deu
kops.sourcefield.plainMARKS, Joe, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 103-114. Lecture Notes in Computer Science. 1984. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10deu
kops.sourcefield.plainMARKS, Joe, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 103-114. Lecture Notes in Computer Science. 1984. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10eng
relation.isAuthorOfPublicationfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
relation.isAuthorOfPublicationab8dd64c-60a5-4662-9603-d40fd0e6c6f3
relation.isAuthorOfPublication.latestForDiscoveryfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
source.bibliographicInfo.fromPage103
source.bibliographicInfo.seriesNumber1984
source.bibliographicInfo.toPage114
source.contributor.editorMarks, Joe
source.identifier.isbn978-3-540-41554-1
source.publisherSpringer Berlin Heidelberg
source.publisher.locationBerlin, Heidelberg
source.relation.ispartofseriesLecture Notes in Computer Science
source.titleGraph Drawing

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
cactus_clustered.pdf
Größe:
264.97 KB
Format:
Adobe Portable Document Format
cactus_clustered.pdf
cactus_clustered.pdfGröße: 264.97 KBDownloads: 296

Sammlungen

Informatik und Informationswissenschaft: Publikationen