Simultaneous Embeddability of Two Partitions

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

ATHENSTÄDT, Jan Christoph, Tanja HARTMANN, Martin NÖLLENBURG, 2014. Simultaneous Embeddability of Two Partitions. 22nd International Symposium, GD 2014. Würzburg, Sep 24, 2014 - Sep 26, 2014. In: CHRISTIAN DUNCAN ..., , ed.. Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers. Berlin [u.a.]:Springer, pp. 64-75. ISBN 978-3-662-45802-0. Available under: doi: 10.1007/978-3-662-45803-7_6

@inproceedings{Athenstadt2014Simul-30029, title={Simultaneous Embeddability of Two Partitions}, year={2014}, doi={10.1007/978-3-662-45803-7_6}, number={8871}, isbn={978-3-662-45802-0}, address={Berlin [u.a.]}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers}, pages={64--75}, editor={Christian Duncan ...}, author={Athenstädt, Jan Christoph and Hartmann, Tanja and Nöllenburg, Martin} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:contributor>Nöllenburg, Martin</dc:contributor> <dc:contributor>Athenstädt, Jan Christoph</dc:contributor> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Hartmann, Tanja</dc:creator> <dcterms:issued>2014</dcterms:issued> <dcterms:available rdf:datatype="">2015-02-25T09:13:48Z</dcterms:available> <bibo:uri rdf:resource=""/> <dcterms:abstract xml:lang="eng">We study the simultaneous embeddability of a pair of partitions of the same underlying set into disjoint blocks. Each element of the set is mapped to a point in the plane and each block of either of the two partitions is mapped to a region that contains exactly those points that belong to the elements in the block and that is bounded by a simple closed curve. We establish three main classes of simultaneous embeddability (weak, strong, and full embeddability) that differ by increasingly strict well-formedness conditions on how different block regions are allowed to intersect. We show that these simultaneous embeddability classes are closely related to different planarity concepts of hypergraphs. For each embeddability class we give a full characterization. We show that (i) every pair of partitions has a weak simultaneous embedding, (ii) it is NP-complete to decide the existence of a strong simultaneous embedding, and (iii) the existence of a full simultaneous embedding can be tested in linear time.</dcterms:abstract> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>Simultaneous Embeddability of Two Partitions</dcterms:title> <dc:creator>Athenstädt, Jan Christoph</dc:creator> <dc:creator>Nöllenburg, Martin</dc:creator> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Hartmann, Tanja</dc:contributor> <dspace:isPartOfCollection rdf:resource=""/> <dc:date rdf:datatype="">2015-02-25T09:13:48Z</dc:date> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account