Planarity of the 2-Level Cactus Model

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

CORNELSEN, Sabine, Yefim DINITZ, Dorothea WAGNER, 2001. Planarity of the 2-Level Cactus Model. Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001. Boltenhagen, Germany, Jun 14, 2001 - Jun 16, 2001. In: BRANDSTÄDT, Andreas, ed. and others. Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001, Proceedings. Berlin:Springer, pp. 91-102. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-42707-0. Available under: doi: 10.1007/3-540-45477-2_10

@inproceedings{Cornelsen2001-10-02Plana-44804, title={Planarity of the 2-Level Cactus Model}, year={2001}, doi={10.1007/3-540-45477-2_10}, number={2204}, isbn={978-3-540-42707-0}, issn={0302-9743}, address={Berlin}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001, Proceedings}, pages={91--102}, editor={Brandstädt, Andreas}, author={Cornelsen, Sabine and Dinitz, Yefim and Wagner, Dorothea} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:abstract xml:lang="eng">The 2-level cactus introduced by Dinitz and Nutov in [5] is a data structure that represents the minimum and minimum+1 edgecuts of an undirected connected multi-graph G in a compact way. In this paper, we study planarity of the 2-level cactus, which can be used, e.g., in graph drawing. We give a new sufficient planarity criterion in terms of projection paths over a spanning subtree of a graph. Using this criterion, we show that the 2-level cactus of G is planar if the cardinality of a minimum edge-cut of G is not equal to 2, 3 or 5. On the other hand, we give examples for non-planar 2-level cacti of graphs with these connectivities.</dcterms:abstract> <dcterms:title>Planarity of the 2-Level Cactus Model</dcterms:title> <dc:contributor>Dinitz, Yefim</dc:contributor> <dc:creator>Wagner, Dorothea</dc:creator> <bibo:uri rdf:resource=""/> <dc:creator>Dinitz, Yefim</dc:creator> <dc:date rdf:datatype="">2019-02-01T13:18:15Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Wagner, Dorothea</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:issued>2001-10-02</dcterms:issued> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dcterms:available rdf:datatype="">2019-02-01T13:18:15Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource=""/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account