Search Results

Documents authored by Kobourov, Stephen

Found 2 Possible Name Variants:

Kobourov, Stephen

Document
DOI: 10.4230/DagRep.13.1.216
Perception in Network Visualization (Dagstuhl Seminar 23051)

Authors: Karsten Klein, Stephen Kobourov, Bernice E. Rogowitz, Danielle Szafir, and Jacob Miller

Published in: Dagstuhl Reports, Volume 13, Issue 1 (2023)

Abstract
Networks are used to model and represent data in many application areas from life sciences to social sciences. Visual network analysis is a crucial tool to improve the understanding of data sets and processes over many levels of complexity, such as different semantic, spatial and temporal granularities. While there is a great deal of work on the algorithmic aspects of network visualization and the computational complexity of the underlying problems, the role and limits of human perception are rarely explicitly investigated and taken into account when designing network visualizations. To address this issue, this Dagstuhl Seminar raised awareness in the network visualization community of the need for more extensive theoretical and empirical understanding of how people perceive and make sense of network visualizations and the significant potential for improving current solutions when perception-based strategies are employed. Likewise, the seminar increased awareness in the perception community that challenges in network research can drive new questions for perception research, for example, in identifying features and patterns in large, often time-varying networks. We brought together researchers from several different communities to initiate a dialogue, foster exchange, discuss the state of the art at this intersection and within the respective fields, identify promising research questions and directions, and start working on selected problems.
Cite as

Karsten Klein, Stephen Kobourov, Bernice E. Rogowitz, Danielle Szafir, and Jacob Miller. Perception in Network Visualization (Dagstuhl Seminar 23051). In Dagstuhl Reports, Volume 13, Issue 1, pp. 216-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{klein_et_al:DagRep.13.1.216,
  author =	{Klein, Karsten and Kobourov, Stephen and Rogowitz, Bernice E. and Szafir, Danielle and Miller, Jacob},
  title =	{{Perception in Network Visualization (Dagstuhl Seminar 23051)}},
  pages =	{216--244},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{1},
  editor =	{Klein, Karsten and Kobourov, Stephen and Rogowitz, Bernice E. and Szafir, Danielle and Miller, Jacob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.1.216},
  URN =		{urn:nbn:de:0030-drops-191220},
  doi =		{10.4230/DagRep.13.1.216},
  annote =	{Keywords: Network Visualization, Graph Drawing, Perception, Cognition}
}
Document
DOI: 10.4230/DagRep.11.3.1
Multi-Level Graph Representation for Big Data Arising in Science Mapping (Dagstuhl Seminar 21152)

Authors: Katy Börner and Stephen Kobourov

Published in: Dagstuhl Reports, Volume 11, Issue 3 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21152 "Multi-Level Graph Representation for Big Data Arising in Science Mapping." The seminar brought together researchers coming from information visualization, psychology, cognitive science, human-computer interaction, graph drawing, computational geometry, and cartography with interests in the "science of science" to discuss novel graph mining and layout algorithms and their application to the development of science mapping standards and services. Due to the pandemic, this was a "hybrid" event with only 5 in-person participants and 25 by-zoom participants from over ten different countries and at least five different time-zones. There were three overview talks and four special presentations (evening webinars) from different communities represented in the seminar. Abstracts of these talks and presentations are collected in this report. Three working groups formed around open research problems related to the seminar topic and we report about their findings.
Cite as

Katy Börner and Stephen Kobourov. Multi-Level Graph Representation for Big Data Arising in Science Mapping (Dagstuhl Seminar 21152). In Dagstuhl Reports, Volume 11, Issue 3, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{borner_et_al:DagRep.11.3.1,
  author =	{B\"{o}rner, Katy and Kobourov, Stephen},
  title =	{{Multi-Level Graph Representation for Big Data Arising in Science Mapping (Dagstuhl Seminar 21152)}},
  pages =	{1--15},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{3},
  editor =	{B\"{o}rner, Katy and Kobourov, Stephen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.3.1},
  URN =		{urn:nbn:de:0030-drops-146885},
  doi =		{10.4230/DagRep.11.3.1},
  annote =	{Keywords: graph theory, graph algorithms, science of science, cartography and map-like representations, network visualization, multi-level semantic zooming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.16
Multi-Level Weighted Additive Spanners

Authors: Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Given a graph G = (V,E), a subgraph H is an additive +β spanner if dist_H(u,v) ≤ dist_G(u,v) + β for all u, v ∈ V. A pairwise spanner is a spanner for which the above inequality is only required to hold for specific pairs P ⊆ V × V given on input; when the pairs have the structure P = S × S for some S ⊆ V, it is called a subsetwise spanner. Additive spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs. In this paper, we consider a multi-level version of the subsetwise additive spanner in weighted graphs motivated by multi-level network design and visualization, where the vertices in S possess varying level, priority, or quality of service (QoS) requirements. The goal is to compute a nested sequence of spanners with the minimum total number of edges. We first generalize the +2 subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several existing algorithms by [Ahmed et al., 2020] for weighted additive spanners, both in terms of runtime and sparsity of the output spanner, when applied as a subroutine to multi-level problem. We provide an experimental evaluation on graphs using several different random graph generators and show that these spanner algorithms typically achieve much better guarantees in terms of sparsity and additive error compared with the theoretical maximum. By analyzing our experimental results, we additionally developed a new technique of changing a certain initialization parameter which provides better spanners in practice at the expense of a small increase in running time.
Cite as

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence. Multi-Level Weighted Additive Spanners. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.SEA.2021.16,
  author =	{Ahmed, Reyan and Bodwin, Greg and Sahneh, Faryad Darabi and Hamm, Keaton and Kobourov, Stephen and Spence, Richard},
  title =	{{Multi-Level Weighted Additive Spanners}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.16},
  URN =		{urn:nbn:de:0030-drops-137885},
  doi =		{10.4230/LIPIcs.SEA.2021.16},
  annote =	{Keywords: multi-level, graph spanner, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.4
Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem

Authors: Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln |T|+1), 𝓁 ρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and 𝓁 is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
Cite as

Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence. Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.ESA.2020.4,
  author =	{Ahmed, Reyan and Sahneh, Faryad Darabi and Hamm, Keaton and Kobourov, Stephen and Spence, Richard},
  title =	{{Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4},
  URN =		{urn:nbn:de:0030-drops-128709},
  doi =		{10.4230/LIPIcs.ESA.2020.4},
  annote =	{Keywords: multi-level, Steiner tree, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.7
Computing β-Stretch Paths in Drawings of Graphs

Authors: Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π=f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p∈P and q∈P, the length of the sub-curve of π connecting f(p) with f(q) is at most β||f(p)-f(q)‖, where ‖.‖ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. The βSP also asks that we output P if it exists. The βSP quantifies a notion of "near straightness" for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε>0, β∈O(poly(log |V(G)|)), and s,t∈V(G), outputs a β-stretch path between s and t, if a (1-ε)β-stretch path between s and t exists in the drawing.
Cite as

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell. Computing β-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SWAT.2020.7,
  author =	{Arkin, Esther M. and Sahneh, Faryad Darabi and Efrat, Alon and Frank, Fabian and Fulek, Radoslav and Kobourov, Stephen and Mitchell, Joseph S. B.},
  title =	{{Computing \beta-Stretch Paths in Drawings of Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.7},
  URN =		{urn:nbn:de:0030-drops-122540},
  doi =		{10.4230/LIPIcs.SWAT.2020.7},
  annote =	{Keywords: stretch factor, dilation, geometric spanners}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.51
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Authors: Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.
Cite as

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mamano_et_al:LIPIcs.ISAAC.2019.51,
  author =	{Mamano, Nil and Efrat, Alon and Eppstein, David and Frishberg, Daniel and Goodrich, Michael T. and Kobourov, Stephen and Matias, Pedro and Polishchuk, Valentin},
  title =	{{New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51},
  URN =		{urn:nbn:de:0030-drops-115477},
  doi =		{10.4230/LIPIcs.ISAAC.2019.51},
  annote =	{Keywords: Nearest-neighbors, Nearest-neighbor chain, motorcycle graph, straight skeleton, multi-fragment algorithm, Euclidean TSP, Steiner TSP}
}
Document
DOI: 10.4230/DagRep.2.6.51
Putting Data on the Map (Dagstuhl Seminar 12261)

Authors: Stephen Kobourov, Alexander Wolff, and Frank van Ham

Published in: Dagstuhl Reports, Volume 2, Issue 6 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12261 ``Putting Data on the Map''.
Cite as

Stephen Kobourov, Alexander Wolff, and Frank van Ham. Putting Data on the Map (Dagstuhl Seminar 12261). In Dagstuhl Reports, Volume 2, Issue 6, pp. 51-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{kobourov_et_al:DagRep.2.6.51,
  author =	{Kobourov, Stephen and Wolff, Alexander and van Ham, Frank},
  title =	{{Putting Data on the Map (Dagstuhl Seminar 12261)}},
  pages =	{51--76},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{6},
  editor =	{Kobourov, Stephen and Wolff, Alexander and van Ham, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.51},
  URN =		{urn:nbn:de:0030-drops-37303},
  doi =		{10.4230/DagRep.2.6.51},
  annote =	{Keywords: Information Visualization, Cartography, GIScience, Computational Geometry, Graph Drawing, Cognition}
}
Document
DOI: 10.4230/DagRep.1.5.47
Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191)

Authors: Camil Demetrescu, Michael Kaufmann, Stephen Kobourov, and Petra Mutzel

Published in: Dagstuhl Reports, Volume 1, Issue 5 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11191 ``Graph Drawing with Algorithm Engineering Methods''. We summarize the talks, open problems, and working group discussions.
Cite as

Camil Demetrescu, Michael Kaufmann, Stephen Kobourov, and Petra Mutzel. Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191). In Dagstuhl Reports, Volume 1, Issue 5, pp. 47-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{demetrescu_et_al:DagRep.1.5.47,
  author =	{Demetrescu, Camil and Kaufmann, Michael and Kobourov, Stephen and Mutzel, Petra},
  title =	{{Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191)}},
  pages =	{47--60},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{Demetrescu, Camil and Kaufmann, Michael and Kobourov, Stephen and Mutzel, Petra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.5.47},
  URN =		{urn:nbn:de:0030-drops-32046},
  doi =		{10.4230/DagRep.1.5.47},
  annote =	{Keywords: Algorithm Engineering, Graph Drawing}
}
Document
DOI: 10.4230/DagSemProc.08191.1
08191 Abstracts Collection – Graph Drawing with Applications to Bioinformatics and Social Sciences

Authors: Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
From May 4 to May 9, 2008, the Dagstuhl Seminar 08191 ``Graph Drawing with Applications to Bioinformatics and Social Sciences'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel. 08191 Abstracts Collection – Graph Drawing with Applications to Bioinformatics and Social Sciences. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.1,
  author =	{Borgatti, Stephen and Kobourov, Stephen and Kohlbacher, Oliver and Mutzel, Petra},
  title =	{{08191 Abstracts Collection – Graph Drawing with Applications to Bioinformatics and Social Sciences}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.1},
  URN =		{urn:nbn:de:0030-drops-15547},
  doi =		{10.4230/DagSemProc.08191.1},
  annote =	{Keywords: Graph drawing, visualization, social sciences, bioinformatics}
}
Document
DOI: 10.4230/DagSemProc.08191.2
08191 Executive Summary – Graph Drawing with Applications to Bioinformatics and Social Sciences

Authors: Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
Graph drawing deals with the problem of communicating the structure of relational data through diagrams, or drawings. The ability to represent relational information in a graphical form is a powerful tool which allows to perform analysis through visual exploration to find important patterns, trends, and correlations. Real-world applications such as bioinformatics and sociology pose challenges to the relational visualization because, e.g., semantic information carried by the diagram has to be used for obtaining meaningful layouts and application-specific drawing conventions need to be fulfilled. Moreover, the underlying data often stems from huge data bases, but only a small fraction shall be displayed at a time; the user interactively selects the data to be displayed and explores the graph by expanding interesting and collapsing irrelevant parts. This requires powerful graph exploration tools with navigation capabilities that allow dynamic adaption of the graph layout in real time. In this seminar we focused on the application of graph drawing in two important application domains: bioinformatics and social sciences. We brought together theoreticians and practitioners from these areas and focused on problems concerning interaction with and navigation in large and dynamic networks arising in these application areas; During the seminar, we identified and defined open graph drawing problems that are motivated by practical applications in the targeted application areas, tackled selected open problems, formulated the findings as a first step to the solution, and defined further research directions.
Cite as

Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel. 08191 Executive Summary – Graph Drawing with Applications to Bioinformatics and Social Sciences. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.2,
  author =	{Borgatti, Stephen and Kobourov, Stephen and Kohlbacher, Oliver and Mutzel, Petra},
  title =	{{08191 Executive Summary – Graph Drawing with Applications to Bioinformatics and Social Sciences}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.2},
  URN =		{urn:nbn:de:0030-drops-15523},
  doi =		{10.4230/DagSemProc.08191.2},
  annote =	{Keywords: Graph drawing, visualization, social sciences, bioinformatics}
}
Document
DOI: 10.4230/DagSemProc.08191.4
08191 Working Group Report – Visualization of Trajectories

Authors: Stephen Borgatti, Ulrik Brandes, Michael Kaufmann, Stephen Kobourov, Anna Lubiw, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
We considered the following problem: Given a set of vertices V and a set of paths P, where each path is a sequence of vertices, represent these paths somehow. We explored representations in different dimensions and with different conditions on the paths.
Cite as

Stephen Borgatti, Ulrik Brandes, Michael Kaufmann, Stephen Kobourov, Anna Lubiw, and Dorothea Wagner. 08191 Working Group Report – Visualization of Trajectories. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.4,
  author =	{Borgatti, Stephen and Brandes, Ulrik and Kaufmann, Michael and Kobourov, Stephen and Lubiw, Anna and Wagner, Dorothea},
  title =	{{08191 Working Group Report – Visualization of Trajectories}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.4},
  URN =		{urn:nbn:de:0030-drops-15558},
  doi =		{10.4230/DagSemProc.08191.4},
  annote =	{Keywords: Graph drawing, trajectories, paths}
}
Document
DOI: 10.4230/DagSemProc.05191.1
05191 Abstracts Collection – Graph Drawing

Authors: Michael Jünger, Petra Mutzel, and Stephen Kobourov

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

Abstract
From 08.05.05 to 13.05.05, the Dagstuhl Seminar 05191 ``Graph Drawing'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Michael Jünger, Petra Mutzel, and Stephen Kobourov. 05191 Abstracts Collection – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.1,
  author =	{J\"{u}nger, Michael and Mutzel, Petra and Kobourov, Stephen},
  title =	{{05191 Abstracts Collection – Graph Drawing}},
  booktitle =	{Graph Drawing},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.1},
  URN =		{urn:nbn:de:0030-drops-3485},
  doi =		{10.4230/DagSemProc.05191.1},
  annote =	{Keywords: Graph Drawing, Visualization, Layout Algorithms, Interactive Visualization}
}
Document
DOI: 10.4230/DagSemProc.05191.2
05191 Executive Summary – Graph Drawing

Authors: Michael Jünger, Stephen Kobourov, and Petra Mutzel

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

Abstract
This paper summarizes the topics, aims, and achievements of the Dagstuhl Seminar 05191 on Graph Drawing.
Cite as

Michael Jünger, Stephen Kobourov, and Petra Mutzel. 05191 Executive Summary – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.2,
  author =	{J\"{u}nger, Michael and Kobourov, Stephen and Mutzel, Petra},
  title =	{{05191 Executive Summary – Graph Drawing}},
  booktitle =	{Graph Drawing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.2},
  URN =		{urn:nbn:de:0030-drops-3420},
  doi =		{10.4230/DagSemProc.05191.2},
  annote =	{Keywords: Graph drawing}
}

Kobourov, Stephen G.

Document
DOI: 10.4230/LIPIcs.GD.2024.16
GraphTrials: Visual Proofs of Graph Properties

Authors: Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer’s perception, in particular, pre-attentive processing (e. g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes.
Cite as

Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber. GraphTrials: Visual Proofs of Graph Properties. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.GD.2024.16,
  author =	{F\"{o}rster, Henry and Klesen, Felix and Dwyer, Tim and Eades, Peter and Hong, Seok-Hee and Kobourov, Stephen G. and Liotta, Giuseppe and Misue, Kazuo and Montecchiani, Fabrizio and Pastukhov, Alexander and Schreiber, Falk},
  title =	{{GraphTrials: Visual Proofs of Graph Properties}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.16},
  URN =		{urn:nbn:de:0030-drops-213005},
  doi =		{10.4230/LIPIcs.GD.2024.16},
  annote =	{Keywords: Graph Visualization, Theory of Visualization, Visual Proof}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.21
The Perception of Stress in Graph Drawings

Authors: Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, Stephen G. Kobourov, and Jacob Miller

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Most of the common graph layout principles (a.k.a. "aesthetics") on which many graph drawing algorithms are based are easy to define and to perceive. For example, the number of pairs of edges that cross each other, how symmetric a drawing looks, the aspect ratio of the bounding box, or the angular resolution at the nodes. The extent to which a graph drawing conforms to these principles can be determined by looking at how it is drawn - that is, by looking at the marks on the page - without consideration for the underlying structure of the graph. A key layout principle is that of optimising "stress", the basis for many algorithms such as the popular Kamada & Kawai algorithm and several force-directed algorithms. The stress of a graph drawing is, loosely speaking, the extent to which the geometric distance between each pair of nodes is proportional to the shortest path between them - over the whole graph drawing. The definition of stress therefore relies on the underlying structure of the graph (the "paths") in a way that other layout principles do not, making stress difficult to describe to novices unfamiliar with graph drawing principles, and, we believe, difficult to perceive. We conducted an experiment to see whether people (novices as well as experts) can see stress in graph drawings, and found that it is possible to train novices to "see" stress - even if their perception strategies are not based on the definitional concepts.
Cite as

Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, Stephen G. Kobourov, and Jacob Miller. The Perception of Stress in Graph Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mooney_et_al:LIPIcs.GD.2024.21,
  author =	{Mooney, Gavin J. and Purchase, Helen C. and Wybrow, Michael and Kobourov, Stephen G. and Miller, Jacob},
  title =	{{The Perception of Stress in Graph Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.21},
  URN =		{urn:nbn:de:0030-drops-213051},
  doi =		{10.4230/LIPIcs.GD.2024.21},
  annote =	{Keywords: Stress, Graph Drawing, Visual Perception}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.15
Multi-Level Steiner Trees

Authors: Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with non-negative edge costs and a set of terminals T subseteq V. The objective is to find a minimum-cost edge set E' subseteq E that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of rho = ln(4)+epsilon < 1.39. In this paper, we study a natural generalization, the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals T_1 subset ... subset T_k subseteq V, compute nested edge sets E_1 subseteq ... subseteq E_k subseteq E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under names such as Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using four types of graph generators. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is small (k <= 22), which works well for applications such as designing multi-level infrastructure or network visualization.
Cite as

Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.SEA.2018.15,
  author =	{Ahmed, Reyan and Angelini, Patrizio and Sahneh, Faryad Darabi and Efrat, Alon and Glickenstein, David and Gronemann, Martin and Heinsohn, Niklas and Kobourov, Stephen G. and Spence, Richard and Watkins, Joseph and Wolff, Alexander},
  title =	{{Multi-Level Steiner Trees}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.15},
  URN =		{urn:nbn:de:0030-drops-89506},
  doi =		{10.4230/LIPIcs.SEA.2018.15},
  annote =	{Keywords: Approximation algorithm, Steiner tree, multi-level graph representation}
}
Document
DOI: 10.4230/DagRep.6.11.35
Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)

Authors: Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pach

Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)

Abstract
This report summarizes Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics'' and documents the talks and discussions. The seminar brought together 29 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. The common interest was in the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with three introductory talks by experts in the different fields. Abstracts of these talks are collected in this report. Next we discussed and grouped together open research problems about beyond planar graphs, such as their combinatorial structures (e.g, thickness, crossing number, coloring), their topology (e.g., string graph representation), their geometric representations (e.g., straight-line drawing, visibility representation, contact representation), and applications (e.g., algorithms for real-world network visualization). Four working groups were formed and a report from each group is included here.
Cite as

Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pach. Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452). In Dagstuhl Reports, Volume 6, Issue 11, pp. 35-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{hong_et_al:DagRep.6.11.35,
  author =	{Hong, Sok-Hee and Kaufmann, Michael and Kobourov, Stephen G. and Pach, J\'{a}nos},
  title =	{{Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)}},
  pages =	{35--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Hong, Sok-Hee and Kaufmann, Michael and Kobourov, Stephen G. and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.11.35},
  URN =		{urn:nbn:de:0030-drops-70385},
  doi =		{10.4230/DagRep.6.11.35},
  annote =	{Keywords: graph drawing, graph algorithms, graph theory, geometric algorithms, combinatorial geometry, visualization}
}
Document
DOI: 10.4230/DagRep.3.4.34
Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)

Authors: Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13151 "Drawing Graphs and Maps with Curves". The seminar brought together 34 researchers from different areas such as graph drawing, information visualization, computational geometry, and cartography. During the seminar we started with seven overview talks on the use of curves in the different communities represented in the seminar. Abstracts of these talks are collected in this report. Six working groups formed around open research problems related to the seminar topic and we report about their findings. Finally, the seminar was accompanied by the art exhibition Bending Reality: Where Arc and Science Meet with 40 exhibits contributed by the seminar participants.
Cite as

Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud. Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151). In Dagstuhl Reports, Volume 3, Issue 4, pp. 34-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{kobourov_et_al:DagRep.3.4.34,
  author =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  title =	{{Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)}},
  pages =	{34--68},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.4.34},
  URN =		{urn:nbn:de:0030-drops-41680},
  doi =		{10.4230/DagRep.3.4.34},
  annote =	{Keywords: graph drawing, information visualization, computational cartography, computational geometry}
}
Document
DOI: 10.4230/DagSemProc.05361.7
Force-Directed Approaches to Sensor Network Localization

Authors: Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor applications, the cost of this solution for large networks is prohibitively high. We consider static and mobile network localization approaches that make use of the local neighborhood information, in the form of relative distances and angles to nearby nodes, gathered through simpler and less costly devices (RF, ultrasound based range sensors, or antenna arrays). Our algorithms do not make any assumptions about the existence of anchor nodes capable of locating themselves, nor about the knowledge of an initial localization to start with. Instead, we rely on a multi-scale force-directed approach, utilizing range and angle data through dead reckoning. We show that our localization algorithms are robust and scale well with network size.
Cite as

Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer. Force-Directed Approaches to Sensor Network Localization. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kobourov_et_al:DagSemProc.05361.7,
  author =	{Kobourov, Stephen G. and Efrat, Alon and Forrester, David and Iyer, Anand},
  title =	{{Force-Directed Approaches to Sensor Network Localization}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.7},
  URN =		{urn:nbn:de:0030-drops-5693},
  doi =		{10.4230/DagSemProc.05361.7},
  annote =	{Keywords: Sensor network localization, multi-scale force-directed approach, dead reckoning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact