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

Brandes, Ulrik; Cornelsen, Sabine; Wagner, Dorothea

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

Files

cactus_clustered.pdf(264.97 KB)

Date

2002

Authors

Brandes, Ulrik

Cornelsen, Sabine

Wagner, Dorothea

Publication type

Contribution to a conference collection

Published in

Graph Drawing / Marks, Joe (ed.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. - (Lecture Notes in Computer Science ; 1984). - pp. 103-114. - ISBN 978-3-540-41554-1

Abstract

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.

Subject (DDC)

004 Computer Science

Cite This

ISO 690

BRANDES, 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, pp. 103-114. ISBN 978-3-540-41554-1. Available under: doi: 10.1007/3-540-44541-2_10

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}
}

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>

Bibliography of Konstanz

No