Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles
Lade...
Dateien
Datum
2005
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
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Journal of Graph Algorithms and Applications. 2005, 9(1), pp. 99-115. ISSN 1526-1719. Available under: doi: 10.1007/978-3-540-24595-7_33
Zusammenfassung
A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut in the family 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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
BRANDES, Ulrik, Sabine CORNELSEN, Dorothea WAGNER, 2005. Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles. In: Journal of Graph Algorithms and Applications. 2005, 9(1), pp. 99-115. ISSN 1526-1719. Available under: doi: 10.1007/978-3-540-24595-7_33BibTex
@article{Brandes2005Chara-5811, year={2005}, doi={10.1007/978-3-540-24595-7_33}, title={Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles}, number={1}, volume={9}, issn={1526-1719}, journal={Journal of Graph Algorithms and Applications}, pages={99--115}, 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/5811"> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:16Z</dc:date> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Wagner, Dorothea</dc:creator> <dcterms:title>Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles</dcterms:title> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5811/1/Axis_Parallel.pdf"/> <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 in the family 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> <dc:format>application/pdf</dc:format> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:16Z</dcterms:available> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5811"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Brandes, Ulrik</dc:creator> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5811/1/Axis_Parallel.pdf"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dcterms:issued>2005</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:contributor>Brandes, Ulrik</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Wagner, Dorothea</dc:contributor> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dc:creator>Cornelsen, Sabine</dc:creator> <dcterms:bibliographicCitation>First publ. in: Journal of Graph Algorithms and Applications 9 (2005), 1, pp. 99-115</dcterms:bibliographicCitation> </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