Completely connected clustered graphs

Cornelsen, Sabine; Wagner, Dorothea

Completely connected clustered graphs

Files

There are no files associated with this item.

Date

2006

Authors

Cornelsen, Sabine

Wagner, Dorothea

DOI (citable link)

10.1016/j.jda.2005.06.002

Collections

Informatik und Informationswissenschaft

Publication type

Journal article

Publication status

Published

Published in

Journal of Discrete Algorithms ; 4 (2006), 2. - pp. 313-323. - ISSN 1570-8667

Abstract

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.

Subject (DDC)

004 Computer Science

Keywords

Graph drawing, Clustered graphs, Planar graphs

Cite This

ISO 690

CORNELSEN, Sabine, Dorothea WAGNER, 2006. Completely connected clustered graphs. In: Journal of Discrete Algorithms. 4(2), pp. 313-323. ISSN 1570-8667. Available under: doi: 10.1016/j.jda.2005.06.002

BibTex

@article{Cornelsen2006-06Compl-44800,
  year={2006},
  doi={10.1016/j.jda.2005.06.002},
  title={Completely connected clustered graphs},
  number={2},
  volume={4},
  issn={1570-8667},
  journal={Journal of Discrete Algorithms},
  pages={313--323},
  author={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/44800">
    <dc:language>eng</dc:language>
    <dcterms:issued>2006-06</dcterms:issued>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44800"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T12:58:02Z</dcterms:available>
    <dcterms:title>Completely connected clustered graphs</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T12:58:02Z</dc:date>
    <dcterms:abstract xml:lang="eng">Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.</dcterms:abstract>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

No

Refereed

Unknown