caa a22 4500 445804343 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-010-9433-x doi (NATIONALLICENCE)springer-10.1007/s00453-010-9433-x Colored Simultaneous Geometric Embeddings andUniversal Pointsets [Elektronische Daten] [Ulrik Brandes, Cesim Erten, Alejandro Estrella-Balderrama, J. Fowler, Fabrizio Frati, Markus Geyer, Carsten Gutwenger, Seok-Hee Hong, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, Petra Mutzel, Antonios Symvonis] Universal pointsets can be used for visualizing multiple relationships on the same set of objects or for visualizing dynamic graph processes. In simultaneous geometric embeddings, the same point in the plane is used to represent the same object as a way to preserve the viewer's mental map. In colored simultaneous embeddings this restriction is relaxed, by allowing a given object to map to a subset of points in the plane. Specifically, consider a set of graphs on the same set of n vertices partitioned into k colors. Finding a corresponding set of k-colored points in the plane such that each vertex is mapped to a point of the same color so as to allow a straight-line plane drawing of each graph is the problem of colored simultaneous geometric embedding. For n-vertex paths, we show that there exist universal pointsets of size n, colored with two or three colors. We use this result to construct colored simultaneous geometric embeddings for a 2-colored tree together with any number of 2-colored paths, and more generally, a2-colored outerplanar graph together with any number of 2-colored paths. For n-vertex trees, we construct small near-universal pointsets for 3-colored caterpillars of size n, 3-colored radius-2 stars of size n+3, and 2-colored spiders of size n. For n-vertex outerplanar graphs, we show that these same universal pointsets also suffice for 3-colored K 3-caterpillars, 3-colored K 3-stars, and 2-colored fans, respectively. We also present several negative results, showing that there exist a 2-colored planar graph and pseudo-forest, three 3-colored outerplanar graphs, four 4-colored pseudo-forests, three 5-colored pseudo-forests, five 5-colored paths, two 6-colored biconnected outerplanar graphs, three 6-colored cycles, four 6-colored paths, and three 9-colored paths that cannot be simultaneously embedded. Springer Science+Business Media, LLC, 2010 Simultaneous embedding nationallicence Simultaneous geometric embedding nationallicence Colored simultaneous embedding nationallicence Universal pointsets nationallicence Graph drawing nationallicence Brandes Ulrik Department of Computer & Information Science, University of Konstanz, Konstanz, Germany aut Erten Cesim Department of Computer Science, Isik University, Istanbul, Turkey aut Estrella-Balderrama Alejandro Department of Computer Science, University of Arizona, Tucson, AZ, USA aut Fowler J. Department of Computer Science, University of Arizona, Tucson, AZ, USA aut Frati Fabrizio Department of Computer Science, University of Roma Tre, Rome, Italy aut Geyer Markus Wilhelm-Schickard-Institute of Computer Science, University of Tübingen, Tübingen, Germany aut Gutwenger Carsten Department of Computer Science, University of Dortmund, Dortmund, Germany aut Hong Seok-Hee NICTA Ltd. and School of Information Technologies, University of Sydney, Sydney, Australia aut Kaufmann Michael Wilhelm-Schickard-Institute of Computer Science, University of Tübingen, Tübingen, Germany aut Kobourov Stephen Department of Computer Science, University of Arizona, Tucson, AZ, USA aut Liotta Giuseppe School of Computing, University of Perugia, Perugia, Italy aut Mutzel Petra Department of Computer Science, University of Dortmund, Dortmund, Germany aut Symvonis Antonios School of Applied Mathematics & Physical Sciences, National Technical University of Athens, Athens, Greece aut Algorithmica Springer-Verlag 60/3(2011-07-01), 569-592 0178-4617 60:3<569 2011 60 453 https://doi.org/10.1007/s00453-010-9433-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9433-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Brandes Ulrik Department of Computer & Information Science, University of Konstanz, Konstanz, Germany aut NATIONALLICENCE 700 1- Erten Cesim Department of Computer Science, Isik University, Istanbul, Turkey aut NATIONALLICENCE 700 1- Estrella-Balderrama Alejandro Department of Computer Science, University of Arizona, Tucson, AZ, USA aut NATIONALLICENCE 700 1- Fowler J. Department of Computer Science, University of Arizona, Tucson, AZ, USA aut NATIONALLICENCE 700 1- Frati Fabrizio Department of Computer Science, University of Roma Tre, Rome, Italy aut NATIONALLICENCE 700 1- Geyer Markus Wilhelm-Schickard-Institute of Computer Science, University of Tübingen, Tübingen, Germany aut NATIONALLICENCE 700 1- Gutwenger Carsten Department of Computer Science, University of Dortmund, Dortmund, Germany aut NATIONALLICENCE 700 1- Hong Seok-Hee NICTA Ltd. and School of Information Technologies, University of Sydney, Sydney, Australia aut NATIONALLICENCE 700 1- Kaufmann Michael Wilhelm-Schickard-Institute of Computer Science, University of Tübingen, Tübingen, Germany aut NATIONALLICENCE 700 1- Kobourov Stephen Department of Computer Science, University of Arizona, Tucson, AZ, USA aut NATIONALLICENCE 700 1- Liotta Giuseppe School of Computing, University of Perugia, Perugia, Italy aut NATIONALLICENCE 700 1- Mutzel Petra Department of Computer Science, University of Dortmund, Dortmund, Germany aut NATIONALLICENCE 700 1- Symvonis Antonios School of Applied Mathematics & Physical Sciences, National Technical University of Athens, Athens, Greece aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 569-592 0178-4617 60:3<569 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer