Yazar "Kobourov, Stephen G." seçeneğine göre listele
Listeleniyor 1 - 4 / 4
Sayfa Başına Sonuç
Sıralama seçenekleri
Yayın Colored simultaneous geometric embeddings(Springer-Verlag Berlin, 2007) Brandes, Ulrik; Erten, Cesim; Fowler, J. Joseph; Frati, Fabrizio; Geyer, Markus; Gutwenger, Carsten; Hong, Seok-Hee; Kaufmann, Michael; Kobourov, Stephen G.; Liotta, Giuseppe; Mutzel, Petra; Symvonis, AntoniosWe 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.Yayın Colored simultaneous geometric embeddings and universal pointsets(Springer, 2011-07) Brandes, Ulrik; Erten, Cesim; Estrella-Balderrama, Alejandro; Fowler, J. Joseph; Frati, Fabrizio; Geyer, Markus; Gutwenger, Carsten; Hong, Seok-Hee; Kaufmann, Michael; Kobourov, Stephen G.; Liotta, Giuseppe; Mutzel, Petra; Symvonis, AntoniosUniversal 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, a 2-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.Yayın Force-directed approaches to sensor localization(SIAM, 2006) Efrat, Alon; Forrester, David; Iyer, Anand; Kobourov, Stephen G.; Erten, CesimWe consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.Yayın Force-directed approaches to sensor localization(Assoc Computing Machinery, 2010-09) Efrat, Alon; Forrester, David; Iyer, Anand; Kobourov, Stephen G.; Erten, Cesim; Kılıç, Yasin OzanAs the number of applications of sensor networks increases, so does the interest in sensor network localization, that is, in recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this article, we consider the anchor-free localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor's neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with nonconvex or nonsimple underlying topology. Moreover, the distributed nature of the problem makes some of the centralized techniques inapplicable in distributed settings. To address these problems we describe a multiscale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are augmented with a multiscale extension to handle the scalability issue and with a dead-reckoning extension to overcome the problems arising with nonsimple topologies. Furthermore, we show that the distributed version of the MSDR algorithm performs as well as, if not better than, its centralized counterpart, as shown by the quality of the layout, measured in terms of the accuracy of the computed pairwise distances between sensors in the network.
