Publikation:

Planarity of Overlapping Clusterings Including Unions of Two Partitions

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2017

Autor:innen

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.7155/jgaa.00450
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

European Union (EU): 319209

Projekt

NEXUS 1492
Open Access-Veröffentlichung

Sammlungen

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

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

Journal of Graph Algorithms and Applications. 2017, 21(6), pp. 1057-1089. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00450

Zusammenfassung

We consider clustered planarity with overlapping clusters as introduced by Didimo et al. [14]. It can be deduced from a proof in Athenstädt et al. [2] that the problem is NP-complete, even if restricted to instances where the underlying graph is 2-connected, the set of clusters is the union of two partitions and each cluster contains at most two connected components while their complements contain at most three connected components.
In this paper, we show that clustered planarity with overlapping clusters can be solved in polynomial time if each cluster induces a connected subgraph. It can be solved in linear time if the set of clusters is the union of two partitions of the vertex set such that, for each cluster, both the cluster and its complement induce connected subgraphs.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690ATHENSTÄDT, Jan C., Sabine CORNELSEN, 2017. Planarity of Overlapping Clusterings Including Unions of Two Partitions. In: Journal of Graph Algorithms and Applications. 2017, 21(6), pp. 1057-1089. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00450
BibTex
@article{Athenstadt2017Plana-44791,
  year={2017},
  doi={10.7155/jgaa.00450},
  title={Planarity of Overlapping Clusterings Including Unions of Two Partitions},
  number={6},
  volume={21},
  journal={Journal of Graph Algorithms and Applications},
  pages={1057--1089},
  author={Athenstädt, Jan C. and Cornelsen, Sabine}
}
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/44791">
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:abstract xml:lang="eng">We consider clustered planarity with overlapping clusters as introduced by Didimo et al. [14]. It can be deduced from a proof in Athenstädt et al. [2] that the problem is NP-complete, even if restricted to instances where the underlying graph is 2-connected, the set of clusters is the union of two partitions and each cluster contains at most two connected components while their complements contain at most three connected components.&lt;br /&gt;In this paper, we show that clustered planarity with overlapping clusters can be solved in polynomial time if each cluster induces a connected subgraph. It can be solved in linear time if the set of clusters is the union of two partitions of the vertex set such that, for each cluster, both the cluster and its complement induce connected subgraphs.</dcterms:abstract>
    <dc:contributor>Athenstädt, Jan C.</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-31T13:31:58Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Athenstädt, Jan C.</dc:creator>
    <dcterms:title>Planarity of Overlapping Clusterings Including Unions of Two Partitions</dcterms:title>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44791"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2017</dcterms:issued>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-31T13:31:58Z</dc:date>
  </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
Ja
Diese Publikation teilen