Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles

Brandes, Ulrik; Cornelsen, Sabine; Wagner, Dorothea

Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles

Files

bcw_cfcra_04.pdf(870.23 KB)

Date

2004

Authors

Brandes, Ulrik

Cornelsen, Sabine

Wagner, Dorothea

Publication type

Contribution to a conference collection

Published in

Graph drawing : 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003; revised papers / Liotta, Giuseppe (ed.). - Berlin [u.a.] : Springer, 2004. - (Lecture notes in computer science ; 2912). - pp. 357-368. - ISBN 978-3-540-20831-0

Abstract

A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa. We show that the families of cuts that admit a drawing in which every cut is represented by an axis-parallel rectangle are exactly those that have a cactus model that can be rooted such that edges of the graph that cross a cycle of the cactus point to the root. This includes the family of all minimum cuts of a graph. The proof also yields an efficient algorithm to construct a drawing with axis-parallel rectangles if it exists.

Subject (DDC)

004 Computer Science

Cite This

ISO 690

BRANDES, Ulrik, Sabine CORNELSEN, Dorothea WAGNER, 2004. Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles. In: LIOTTA, Giuseppe, ed.. Graph drawing : 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003; revised papers. Berlin [u.a.]:Springer, pp. 357-368. ISBN 978-3-540-20831-0

BibTex

@inproceedings{Brandes2004Chara-5777,
  year={2004},
  title={Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles},
  number={2912},
  isbn={978-3-540-20831-0},
  publisher={Springer},
  address={Berlin [u.a.]},
  series={Lecture notes in computer science},
  booktitle={Graph drawing : 11th International Symposium, GD 2003, Perugia, Italy, September 21 - 24, 2003; revised papers},
  pages={357--368},
  editor={Liotta, Giuseppe},
  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/5777">
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5777/1/bcw_cfcra_04.pdf"/>
    <dcterms:bibliographicCitation>First publ. in: Lecture notes in computer science, No. 2912 (2004), pp. 357-368</dcterms:bibliographicCitation>
    <dcterms:abstract xml:lang="eng">A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa. We show that the families of cuts that admit a drawing in which every cut is represented by an axis-parallel rectangle are exactly those that have a cactus model that can be rooted such that edges of the graph that cross a cycle of the cactus point to the root. This includes the family of all minimum cuts of a graph. The proof also yields an efficient algorithm to construct a drawing with axis-parallel rectangles if it exists.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:title>Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles</dcterms:title>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:02Z</dc:date>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5777/1/bcw_cfcra_04.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2004</dcterms:issued>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:02Z</dcterms:available>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5777"/>
    <dc:creator>Wagner, Dorothea</dc:creator>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

Yes