https://algo.iti.kit.edu/ 2026-05-13T15:15:36+00:00 https://algo.iti.kit.edu/ https://algo.iti.kit.edu/_media/favicon.ico text/html 2009-01-12T17:38:04+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/ccg Cover Contact Graphs Publications * Nieves Atienza, Natalia de Castro, Carmen Cortés, M. Ángeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, Maria Trinidad Villar, and Alexander Wolff. Cover contact graphs. In S.-H. Hong and T. Nishizeki, editors, text/html 2009-01-12T17:42:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/cfc Configuratione with Few Crossings Crossing-minimum spanning trees Given a connected graph G with its embedding in the plane, does G contain a crossing-free spanning tree? This problem is known to be NP-complete. We show that the problem of finding a spanning tree with the minimum number of edge crossings is even NP-hard to approximate. We further show that this optimization problem is fixed-parameter tractable. We also give a mixed-integer formulation and a simple, but efficient and effective … text/html 2009-01-12T17:32:15+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/cvd Voronoi Diagram for the City-Metric Voronoi regions that take roads into account Given a set S of n point sites in the plane, the City Voronoi diagram partitions the plane into the Voronoi regions of the sites, with respect to the City metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the City Voronoi diagram (incl… text/html 2009-01-12T17:30:21+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/flo Reporting Flock Patterns Detecting flocks by range queries in higher-dim. space A study in Alaska gave the motivation for this work: caribous had been endowed with GPS collars in order to trace their positions over a longer period of time. The aim was to detect and report flocks that the single caribous form and to analyze the social behavior of the animals. text/html 2009-01-12T17:40:15+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/gen Morphing of Polygonal Lines Generalization of linear features in interactive maps Depending on the scale objects in a map are displayed with different levels of detail. In cartography the simplification process that finds the right level of detail is known as generalization. Classical (paper) maps are designed for a fixed single scale and generalization is optimized such that the map is as readable as possible at the given scale. In today's web-based and interactive maps, however, the user can… text/html 2009-01-09T14:36:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/index GeoNet Geometric Networks and their Visualization DFG grants WO 758/4-1, 4-2, and 4-3 Group leader: PD Dr. Alexander Wolff * * Members * Research Projects * Publications Project description Geometric networks are the main tool to model flow of traffic, goods or information. They have applications in routing of railway systems, VLSI layout and the analysis of the world wide web. The networks are represented by geometric graphs whose objects (cities, persons, etc.) are points in… text/html 2009-01-12T17:36:59+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/lab Boundary Labeling How to produce easy-to-understand labelings? Boundary labelings are applied, e.g., in order to label places or regions in geographic maps if the direct placement of the labels inside the illustration is impossible or overly reduces legibility. In this case the labels are placed aside the illustration and points and labels are connected by arcs. This yields a labeling problem that also includes graph drawing problems: text/html 2009-01-12T16:40:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/members Members Group leader * PD Dr. Alexander Wolff PhD students * PD Dr. Martin Nöllenburg * Dr. Ignaz Rutter Student helpers * Johannes Franz * Markus Völker Former members * Étienne Schramm * Marc Benkert Former Master students * Dr. rer. nat. Robert Görke * Nikolaus Mutsanas * PD Dr. Martin Nöllenburg * Dr. Ignaz Rutter Former student researchers * Florian Widmann * Moritz Minzlaff text/html 2009-01-12T17:41:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/min Interference Networks Undisturbed communication A set of n communication hosts is to be connected via a communication network. The network should be connected but as each signal transmission causes interferences it should not contain many links. We present an algorithm that constructs an interference-minimal network for the following graph types: spanning tree, t-spanner, and d-hop network. text/html 2009-01-12T17:44:03+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/misc Miscellaneous Publikationen * Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama. Consistent digital rays. In Proc. 24th Annual Symposium on Computational Geometry (SoCG'08), pages 355-364. ACM, 2008. [ bib | pdf ] * Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama. Consistent digital rays. In text/html 2009-01-13T09:54:59+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/mm Metro Maps Summary Metro maps are schematic maps for transportation networks such as metro or subway systems in large cities. However, in contrast to regular city maps, the goal is mainly to find a nice and clear layout of the network topology while geographic accuracy is less important. We formulate a mixed-integer program (MIP) that draws, given a geographic input graph, a metro map optimizing multiple quality criteria. We also show the NP-completeness of the problem. text/html 2009-01-12T17:35:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/mmn Minimum Mannhattan Networks Approximations for the Minimum Manhattan network problem Given a set of n points in the plane, a Manhattan network is the union of vertical and horizontal line segments. such that each pair of points is connected by a shortest rectilinear staircase path, a Manhattan path. We call a network a minimum Manhattan network if the total length of its segments is minimum among all Manhattan networks. The complexity status of the problem is still unknown. text/html 2009-01-12T13:15:19+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/projects Research Projects Metro Maps Metro maps are schematic maps for transportation networks such as metro or subway systems in large cities. » more Reporting Flock Patterns A study in Alaska gave the motivation for this work: caribous had been endowed with GPS collars in order to analyze their behavior. » text/html 2008-12-15T12:41:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/publications Publications Book chapters * Martin Nöllenburg. Geographic visualization. In Andreas Kerren, Achim Ebert, and Joerg Meyer, editors, Human-Centered Visualization Environments, volume 4417 of Lecture Notes in Computer Science, chapter 6, pages 257-294. text/html 2008-12-15T12:42:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/en/projects/geonet/sidebar GeoNet * Introduction * Members * Research Projects * Publications