Colored Simultaneous Geometric Embeddings

Kurzanzeige
dc.contributor.authorBrandes, Ulrik
dc.contributor.authorErten, Cesimdeu
dc.contributor.authorFowler, Jamesdeu
dc.contributor.authorFrati, Fabriziodeu
dc.contributor.authorGeyer, Markusdeu
dc.contributor.authorGutwenger, Carstendeu
dc.contributor.authorHong, Seokheedeu
dc.contributor.authorKaufmann, Michaeldeu
dc.contributor.authorKobourov, Stephen G.deu
dc.contributor.authorLiotta, Giuseppedeu
dc.date.accessioned2011-03-24T16:01:12Zdeu
dc.date.available2011-03-24T16:01:12Zdeu
dc.date.issued2007deu
dc.description.abstractWe introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size n for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size n for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths.eng
dc.description.versionpublished
dc.format.mimetypeapplication/pdfdeu
dc.identifier.citationFirst publ. in: Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON ´07) (LNCS 4598), 2007, pp. 254-263deu
dc.identifier.ppn302326138deu
dc.identifier.urihttp://kops.uni-konstanz.de/handle/123456789/5893
dc.language.isoengdeu
dc.legacy.dateIssued2009deu
dc.rightsAttribution-NonCommercial-NoDerivs 2.0 Generic
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.0/
dc.subject.ddc004deu
dc.titleColored Simultaneous Geometric Embeddingseng
dc.typeINPROCEEDINGSdeu
dspace.entity.typePublication
kops.citation.bibtex
@inproceedings{Brandes2007Color-5893,
  year={2007},
  title={Colored Simultaneous Geometric Embeddings},
  number={4598},
  isbn={978-3-540-73544-1},
  publisher={Springer},
  address={Berlin [u.a.]},
  series={Lecture Notes in Computer Science},
  booktitle={Computing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007},
  pages={254--263},
  author={Brandes, Ulrik and Erten, Cesim and Fowler, James and Frati, Fabrizio and Geyer, Markus and Gutwenger, Carsten and Hong, Seokhee and Kaufmann, Michael and Kobourov, Stephen G. and Liotta, Giuseppe}
}
kops.citation.iso690BRANDES, Ulrik, Cesim ERTEN, James FOWLER, Fabrizio FRATI, Markus GEYER, Carsten GUTWENGER, Seokhee HONG, Michael KAUFMANN, Stephen G. KOBOUROV, Giuseppe LIOTTA, 2007. Colored Simultaneous Geometric Embeddings. In: Computing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007. Berlin [u.a.]: Springer, 2007, pp. 254-263. Lecture Notes in Computer Science. 4598. ISBN 978-3-540-73544-1deu
kops.citation.iso690BRANDES, Ulrik, Cesim ERTEN, James FOWLER, Fabrizio FRATI, Markus GEYER, Carsten GUTWENGER, Seokhee HONG, Michael KAUFMANN, Stephen G. KOBOUROV, Giuseppe LIOTTA, 2007. Colored Simultaneous Geometric Embeddings. In: Computing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007. Berlin [u.a.]: Springer, 2007, pp. 254-263. Lecture Notes in Computer Science. 4598. ISBN 978-3-540-73544-1eng
kops.citation.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/5893">
    <dc:creator>Liotta, Giuseppe</dc:creator>
    <dc:contributor>Kaufmann, Michael</dc:contributor>
    <dc:format>application/pdf</dc:format>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5893/1/beffgghkklms_csge_07.pdf"/>
    <dc:contributor>Hong, Seokhee</dc:contributor>
    <dc:contributor>Geyer, Markus</dc:contributor>
    <dc:creator>Frati, Fabrizio</dc:creator>
    <dc:creator>Kaufmann, Michael</dc:creator>
    <dc:contributor>Fowler, James</dc:contributor>
    <dc:creator>Gutwenger, Carsten</dc:creator>
    <dc:contributor>Erten, Cesim</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5893/1/beffgghkklms_csge_07.pdf"/>
    <dc:creator>Erten, Cesim</dc:creator>
    <dc:contributor>Liotta, Giuseppe</dc:contributor>
    <dc:creator>Geyer, Markus</dc:creator>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:12Z</dc:date>
    <dcterms:abstract xml:lang="eng">We introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size n for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size n for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths.</dcterms:abstract>
    <dcterms:issued>2007</dcterms:issued>
    <dc:contributor>Gutwenger, Carsten</dc:contributor>
    <dc:creator>Hong, Seokhee</dc:creator>
    <dc:contributor>Frati, Fabrizio</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Kobourov, Stephen G.</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:01:12Z</dcterms:available>
    <dcterms:title>Colored Simultaneous Geometric Embeddings</dcterms:title>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON ´07) (LNCS 4598), 2007, pp. 254-263</dcterms:bibliographicCitation>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5893"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:creator>Fowler, James</dc:creator>
    <dc:contributor>Kobourov, Stephen G.</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
  </rdf:Description>
</rdf:RDF>
kops.description.openAccessopenaccessgreen
kops.flag.knbibliographytrue
kops.identifier.nbnurn:nbn:de:bsz:352-opus-73358deu
kops.opus.id7335deu
kops.sourcefield<i>Computing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007</i>. Berlin [u.a.]: Springer, 2007, pp. 254-263. Lecture Notes in Computer Science. 4598. ISBN 978-3-540-73544-1deu
kops.sourcefield.plainComputing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007. Berlin [u.a.]: Springer, 2007, pp. 254-263. Lecture Notes in Computer Science. 4598. ISBN 978-3-540-73544-1deu
kops.sourcefield.plainComputing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007. Berlin [u.a.]: Springer, 2007, pp. 254-263. Lecture Notes in Computer Science. 4598. ISBN 978-3-540-73544-1eng
relation.isAuthorOfPublicationfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
relation.isAuthorOfPublication.latestForDiscoveryfa1660c9-a071-4d01-9bdd-7adcd0e2d7d7
source.bibliographicInfo.fromPage254
source.bibliographicInfo.seriesNumber4598
source.bibliographicInfo.toPage263
source.identifier.isbn978-3-540-73544-1
source.publisherSpringer
source.publisher.locationBerlin [u.a.]
source.relation.ispartofseriesLecture Notes in Computer Science
source.titleComputing and combinatorics : 13th annual international conference, COCOON 2007, Banff, Canada, July 16 - 19, 2007

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
beffgghkklms_csge_07.pdf
Größe:
192.7 KB
Format:
Adobe Portable Document Format
beffgghkklms_csge_07.pdf
beffgghkklms_csge_07.pdfGröße: 192.7 KBDownloads: 331

Sammlungen

Informatik und Informationswissenschaft: Publikationen