Publikation:

Simultaneous Embeddability of Two Partitions

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2014

Autor:innen

Hartmann, Tanja
Nöllenburg, Martin

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-662-45803-7_6
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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, 2014, pp. 64-75. Lecture Notes in Computer Science. 8871. ISBN 978-3-662-45802-0. Available under: doi: 10.1007/978-3-662-45803-7_6

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

22nd International Symposium, GD 2014, 24. Sept. 2014 - 26. Sept. 2014, Würzburg
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690ATHENSTÄDT, Jan C., Tanja HARTMANN, Martin NÖLLENBURG, 2014. Simultaneous Embeddability of Two Partitions. 22nd International Symposium, GD 2014. Würzburg, 24. Sept. 2014 - 26. Sept. 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, 2014, pp. 64-75. Lecture Notes in Computer Science. 8871. ISBN 978-3-662-45802-0. Available under: doi: 10.1007/978-3-662-45803-7_6
BibTex
@inproceedings{Athenstadt2014Simul-30029,
  year={2014},
  doi={10.1007/978-3-662-45803-7_6},
  title={Simultaneous Embeddability of Two Partitions},
  number={8871},
  isbn={978-3-662-45802-0},
  publisher={Springer},
  address={Berlin [u.a.]},
  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 C. and Hartmann, Tanja and Nöllenburg, Martin}
}
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/30029">
    <dc:creator>Nöllenburg, Martin</dc:creator>
    <dc:contributor>Hartmann, Tanja</dc:contributor>
    <dcterms:issued>2014</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-02-25T09:13:48Z</dc:date>
    <dc:contributor>Athenstädt, Jan C.</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Nöllenburg, Martin</dc:contributor>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/30029"/>
    <dc:language>eng</dc:language>
    <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: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>
    <dc:creator>Athenstädt, Jan C.</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-02-25T09:13:48Z</dcterms:available>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:title>Simultaneous Embeddability of Two Partitions</dcterms:title>
    <dc:creator>Hartmann, Tanja</dc:creator>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen