https://www.dagstuhl.de/06481

### November 26 – December 1 , 2006, Dagstuhl Seminar 06481

# Geometric Networks and Metric Space Embeddings

## Organizers

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

## Documents

List of Participants

Dagstuhl's Impact: Documents available

## Summary

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

## Classification

- Data Structures
- Algorithms
- Complexity

## Keywords

- Geometric networks
- Metric space embeddings
- Spanners
- Dilation