2008.08.07 | Else Magård

Title: Geometric Networks - Construction, Analysis and Visualization
Speaker: Alexander Wolff, Eindhoven University of Technology

Abstract: Geometric Networks are graphs whose nodes correspond to points in the
plane.Such networks appear in many applications, from traffic
networks via VLSI chip layout to sensor networks. The construction,
analysis and visualization of geometric networks lead to interesting
problems. Some highlights: for future cities we investigate how to
reach the closest Internetcafe using a network of conveyor belts.
We show that it is hard to draw subway maps - and how to draw them
anyways (with acceptable computational effort). We devise algorithms
that compute maximum (or provably large) matchings in some graph
classes in near-linear time. Finally, we discuss how to continuously
simplify polygonal curves. This has applications in generalizing
roads or rivers on interactive maps.