November 26 – December 1 , 2006, Dagstuhl Seminar 06481

Geometric Networks and Metric Space Embeddings


Joachim Gudmundsson (NICTA – Sydney, AU)
Rolf Klein (Universität Bonn, DE)
Giri Narasimhan (Florida International University – Miami, US)
Michiel Smid (Carleton University – Ottawa, CA)
Alexander Wolff (KIT – Karlsruher Institut für Technologie, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available


This seminar has, for the first time, brought together scientists from three different communities who are actively working on distance problems.

Geometric networks are at the core of any model for the flows of goods, traffic or information. They also play an important role in telecommunication, VLSI design, motion planning (robotics), pattern matching, data compression, bio-informatics (gene analysis), and sensor networks. One is interested in spanners with other useful properties like a linear number of edges, small total edge length, small node degree, few crossings, or small link diameter. Apart from these applications, geometric spanners have had great impact on the construction of approximation algorithms, e.g., for the traveling salesman problem. Such problems have been investigated by researchers in computational geometry and combinatorial optimization. For storage, visualization, and retrieval of high-dimensional data the question of reducing the dimension plays a crucial rôle. This has led to a theory of metric space embeddings that was most actively developed by scientists in discrete geometry and mathematics. Finally, mathematicians and biologists are interested in metric properties and the visualization of phylogenetic networks.

For each of the three fields, a survey talk was given at the seminar (Michiel Smid: Geometric Spanner Networks, Anupam Gupta: Metric Embeddings, Daniel Huson: Application of Phylogenetic Networks in Evolutionary Studies). In addition, twenty-two regular talks were given by the seminar participants. They encouraged a fruitful exchange of ideas and stimulated interesting discussions and co-operations.

The range of interesting topics that came up during this seminar is well documented by the list of problems that were discussed in two open-problem sessions and attacked by small groups of participants in the corresponding problem-solving sessions.

Related Dagstuhl Seminar


  • Data Structures
  • Algorithms
  • Complexity


  • Geometric networks
  • Metric space embeddings
  • Spanners
  • Dilation


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.