Space-Efficient SHARC-Routing (2009)
Brunel, Edith, Delling, Daniel, Gemsa, Andreas, Wagner, Dorothea
Date of Registration: 2007-02-01 (2008)
Chair Prof, Dr. Dorothea Wagner, Marcus Krug
I declare that I have developed and written the enclosed Diploma Thesis completely by myself, and have not used sources or means without declaration in the text. Karlsruhe, 2007-07-09 The problem of...
How to Cluster Evolving Graphs (Extended Abstract) ⋆ (2008)
Marco Gaertler, Robert Görke, Dorothea Wagner, Silke Wagner
Abstract. Clustering is a frequently used tool in the analysis and evaluation of large and complex networks. Most such networks result from or model dynamic processes, thus clustering techniques need...
Timetable Information: Models and Algorithms 1 (2008)
Matthias Müller-hannemann, Frank Schulz, Dorothea Wagner, Christos Zaroliagis
We give an overview of models and efficient algorithms for optimally solving timetable information problems like “given a departure and an arrival station as well as a departure time, which is the...
Partition-Based Speed-Up of Dijkstra’s Algorithm (2008)
Lehrstuhl Prof, Dr. Dorothea Wagner, Fakultät Für Informatik, Birk Schütz, Thomas Willhalm
Determining the shortest path from one node to another in a graph is probably the most popular question in graph theory. If the graph is non-negatively weighted, Dijkstra’s algorithm is the classic...
Generating node coordinates for shortest-path computations in transportation networks (2008)
Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such...
Generating node coordinates for shortest-path computations in transportation networks (2008)
Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such...
Abstract Experimental Comparison of Shortest Path Approaches for Timetable Information ∗ (2008)
Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis
We consider two approaches that model timetable information in public transportation systems as shortestpath problems in weighted graphs. In the time-expanded approach every event at a station, e.g.,...
ANALYSIS OF OVERLAY-UNDERLAY TOPOLOGY CORRELATION USING VISUALIZATION (2008)
Vinay Aggarwal, Anja Feldmann, Marco Gaertler, Robert Görke, Dorothea Wagner
In the design and implementation of the overlay architecture most peer-to-peer (P2P) systems rely on the underlay network to provide them with basic connectivity. Therefore, the intrinsic features of...
Planarity of the 2-Level Cactus Model (2008)
Sabine Cornelsen, Yefim Dinitz, Dorothea Wagner
Abstract. The 2-level cactus introduced by Dinitz and Nutov in [5] is a data structure that represents the minimum and minimum+1 edgecuts of an undirected connected multi-graph G in a compact way. In...
Engineering Graph Clustering: Models and Experimental Evaluation (2008)
Ulrik Brandes, Marco Gaertler, Dorothea Wagner
A promising approach to graph clustering is based on the intuitive notion of intracluster density versus intercluster sparsity. As for the weighted case, clusters should accumulate lots of weight, in...
Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis
Two Approaches for Time-Table Information: A Comparison of Models and Performance \Lambda
Abstract Empirical Design of Geometric Algorithms (2008)
Karsten Weihe, Uhik Br, Dorothea Wagner, Thomas Willhalml
The computer--aided solution to algorithmic problems is becoming more and more important in various application domains. This is in particular true for computational geometry. For example, geomet-ric...
On Modularity Clustering (2008)
Ulrik Br, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, ...
Abstract — Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex...
Generating node coordinates for shortest-path computations in transportation networks (2008)
Ulrik Brandes, Ulrik Br, Frank Schulz, Frank Schulz, Dorothea Wagner, ...
Speed-up techniques that exploit given node coordinates have proven useful for shortestpath computations in transportation networks and geographic information systems. To facilitate the use of such...
EXPLORATIONS INTO THE VISUALIZATION OF POLICY NETWORKS (2008)
Ulrik Br, Patrick Kenis, Jörg Raab, Volker Schneider, Dorothea Wagner
Visualization is an important aspect of both exploration and communication of categorical as well as relational data. Graphical displays of policy networks are particularly attractive, since they...
DISS. ETH NO. 16800 Understanding Ad hoc Networks From Geometry to Mobility (2008)
Dipl Inf. -ing, Eth Zürich, Prof Dr, Roger Wattenhofer, Prof Dr, Rajmohan Rajaraman, ...
born 26.04.1980
Station Location — Complexity and Approximation (2008)
Steffen Mecke, Anita Schöbel, Dorothea Wagner
Abstract. We consider a geometric set covering problem. In its original form it consists of adding stations to an existing geometric transportation network so that each of a given set of settlements...
Generating Node Coordinates for Shortest-Path Computations in Transportation Networks (2008)
Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm
this paper deals only with speed-up techniques that assure the correctness of the result
On Modularity Clustering (2008)
Brandes, Ulrik, Delling, Daniel, Gaertler, Marco, Görke, Robert, Hoefer, Martin, Nikoloski, Zoran, ...
Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems...
08191 Working Group Report -- Visualization of Trajectories (2008)
Borgatti, Stephen, Brandes, Ulrik, Kaufmann, Michael, Kobourov, Stephen, Lubiw, Anna, Wagner, Dorothea
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...
Engineering Time-Expanded Graphs for Faster Timetable Information (2008)
Delling, Daniel, Pajor, Thomas, Wagner, Dorothea
We present an extension of the well-known time-expanded approach for timetable information. By remodeling unimportant stations, we are able to obtain faster query times with less space consumption...
Centrality in Policy Network Drawings (Extended Abstract) (2007)
Ulrik Brandes, Patrick Kenis, Dorothea Wagner
) Ulrik Brandes 1 , Patrick Kenis 2 , and Dorothea Wagner 1 1 University of Konstanz, Faculty of Mathematics and Computer Science 99 9999 9999 9999 9999 9999 9999 9999 9999 9999 -- %stopped_push...
Wiring Edge-Disjoint Layouts (2007)
We consider the wiring or layer assignment problem for edge-disjoint layouts. The wiring problem is well understood for the case that the underlying layout graph is a square grid (see [7]). In this...
Paul Molitor, Uwe Sparmann, Dorothea Wagner
We examine the constrained via minimization problem with pin preassignments (CVMPP) which arises in connection with hierarchical physical synthesis. Let A be a circuit composed of subcircuits B, C,...
Communicating Centrality in Policy Network Drawings (2007)
Ulrik Br, Patrick Kenis, Dorothea Wagner
Abstract—We introduce a network visualization technique that supports an analytical method applied in the social sciences. Policy network analysis is an approach to study policy making structures,...
() Fachbereich Mathematik und Statistik (2007)
I Iiiii, Dorothea Wagner, Thomas Willhalm, Fachbereich Informatik Und Informationswissenschaft
In this paper, we consider Dijkstra's algorithm for the single source single target shortest paths problem in large sparse graphs. The goal is to reduce the response time for online queries by...
Recognizing Bundles in Time Table GraphsApproach (2007)
Annegret Liehers, A Structural, Annegret Liebers, Dorothea Wagner, Dorothea Wagner, ...
We are dealing with an application problem arising in a cooperation with the national German railway company which occurs in the analysis of time table data. The purpose is to infer the underlying...
Sketch-Driven Orthogonal Graph Drawing* (2007)
Ulrik Br, Markus Eiglsperger, Michael Kaufmann, Dorothea Wagner
Abstract. We present an orthogonal graph drawing algorithm that uses a sketchy drawing of the graph as input. While the algorithm produces an orthogonal drawing with few bends in the Kandinsky model...
Planarity of the 2-level Cactus Model (2007)
Sabine Cornelsen, Sabine Cornelsen, Ye M Dinitz, Ye M Dinitz, Dorothea Wagner, Dorothea Wagner
The 2-level cactus introduced by Dinitz and Nutov in [5] is a data structure that represents the minimum and minimum+1 edge-cuts of an undirected connected multigraph G in a compact way. In this...
How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract) (2007)
Ulrik Br, Sabine Cornelsen, Dorothea Wagner
Abstract. We show how to utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a rst approach the cactus is...
Planarity of the 2-level Cactus Model (2007)
Sabine Cornelsen, Ye M Dinitz, Dorothea Wagner
Abstract. The 2-level cactus introduced by Dinitz and Nutov in [5] is a data structure that represents the minimum and minimum+1 edgecuts of an undirected connected multi-graph G in a compact way. In...
PlaNet A Software Package of Algorithms and Heuristics on Planar Networks (2007)
Ulrik Brandes, Gabriele Neyer, Wolfram Schlickenrieder, Dorothea Wagner, Karsten Weihe
We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on...
Wiring Edge-Disjoint Layouts (2007)
Ruth Kuchem, Ruth Kuchem, Dorothea Wagner, Dorothea Wagner
We consider the wiring or layer assignment problem for edge-disjoint layouts. The wiring problem is well understood for the case that the underlying layout graph is a square grid (see [8]). In this...
Fakultat fur Mathematik und Informatik (2007)
Konstanzer Schriften, Mathematik Informatik, Annegret Liebers, Annegret Liebers, Lehrstuhl Prof, Dr. Dorothea Wagner
Given a nite, undirected, simple graph G, we are concerned with operations on G that transform it into a planar graph. We give a survey of results about such operations and related graph parameters....
A Bayesian Paradigm for Dynamic Graph Layout (2007)
Abstract. Dynamic graph layout refers to the layout of graphs that change over time. These changes are due to user interaction, algorithms, or other underlying processes determining the graph....
Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles ⋆ (2007)
Ulrik Br, Sabine Cornelsen, Dorothea Wagner
Abstract. A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa. We show that the families of cuts...
Using Graph Layout to Visualize Train Interconnection Data (2007)
Abstract. We are concerned with the problem of visualizing interconnections in railroad systems. The real-world systems we have to deal with contain connections of thousands of trains. To visualize...
Engineering Graph Clustering : Models and Experimental Evaluation (2007)
Brandes, Ulrik, Gaertler, Marco, Wagner, Dorothea
A promising approach to graph clustering is based on the intuitive notion of intracluster density versus intercluster sparsity. As for the weighted case, clusters should accumulate lots of weight, in...
On Finding Graph Clusterings with Maximum Modularity (2007)
Ulrik Br, Daniel Delling, Marco Gaertler, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner
Abstract. Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex...
On Finding Graph Clusterings with Maximum Modularity (2007)
Ulrik Br, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, ...
Abstract Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems...
Landmark-based routing in dynamic graphs (2007)
Daniel Delling, Dorothea Wagner
Abstract. Many speed-up techniques for route planning in static graphs exist, only few of them are proven to work in a dynamic scenario. Most of them use preprocessed information, which has to be...
Minimizing the area for planar straight-line grid drawings (2007)
Abstract. Straight-line grid drawings of bounded size is a classical topic in graph drawing. The Graph Drawing Challenge 2006 dealt with minimizing the area of planar straight-line grid drawings. In...
Engineering the LabelConstrained Shortest Path Algorithm NDSSL (2007)
Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, Dorothea Wagner
We consider a generalization of the point-to-point (and single-source) shortest path problem to instances where the shortest path must satisfy a formal language constraint. Given an alphabet Σ, a...
On Finding Graph Clusterings with Maximum Modularity (2007)
Brandes, Ulrik, Delling, Daniel, Gaertler, Marco, Görke, Robert, Hoefer, Martin, Nikoloski, Zoran, ...
Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems...
Efficient models for timetable information in public transportation systems (2007)
Pyrga, Evangelia, Schulz, Frank, Wagner, Dorothea, Zaroliagis, Christos
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems (2007)
Bauer, Reinhard, Delling, Daniel, Wagner, Dorothea
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also...
Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks (2006)
Katz, Bastian, Gaertler, Marco, Wagner, Dorothea
Many applications in sensor networks require positional information of the sensors. Recovering node positions is closely related to graph realization problems for geometric graphs. Here, we address...
High-performance multi-level graphs (2006)
Daniel Delling, Martin Holzer, Kirill Müller, Frank Schulz, Dorothea Wagner
Shortest-path computation is a frequent task in practice. Owing to ever-growing real-world graphs, there is a constant need for faster algorithms. In the course of time, a large number of techniques...
High-performance multi-level graphs (2006)
Daniel Delling, Martin Holzer, Kirill Müller, Frank Schulz, Dorothea Wagner
Shortest-path computation is a frequent task in practice. Owing to ever-growing realworld graphs, there is a constant need for faster algorithms. In the course of time, a large number of techniques...
Engineering multi-level overlay graphs for shortest-path queries (2006)
Martin Holzer, Frank Schulz, Dorothea Wagner
An overlay graph of a given graph G = (V, E) on a subset S ⊆ V is a graph with vertex set S and edges corresponding to shortest paths in G. In particular, we consider variations of the multi-level...
Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks (2006)
Bastian Katz, Marco Gaertler, Dorothea Wagner
Abstract. Many applications in sensor networks require positional information of the sensors. Recovering node positions is closely related to graph realization problems for geometric graphs. Here, we...
Generating significant graph clusterings (2006)
Daniel Delling, Marco Gaertler, Dorothea Wagner
Abstract. Many applications such as experimental evaluations of clustering algorithms require the existence of a significant reference clustering. This task is dual to finding significant clusterings...
Engineering multi-level overlay graphs for shortest-path queries (2006)
Martin Holzer, Frank Schulz, Dorothea Wagner
An overlay graph of a given graph G =(V,E) on a subset S ⊆ V is a graph with vertex set S that preserves some property of G. In particular, we consider variations of the multi-level overlay graph...
Fast computation of distance tables using highway hierarchies (2006)
Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner
This technical report considers the problem of computing distances of shortest paths between all pairs of nodes from given sets of sources and targets. The straightforward method to solve this is to...
A hybrid model for drawing dynamic and evolving graphs (2006)
Marco Gaertler, Dorothea Wagner
Abstract. Dynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative...
Highway hierarchies star (2006)
Daniel Delling, Peter S, Dominik Schultes, Dorothea Wagner
Abstract. We study two speedup techniques for route planning in road networks: highway hierarchies (HH) and goal directed search using landmarks (ALT). It turns out that there are several interesting...
Implementations of routing algorithms for transportation networks (2006)
Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, Dorothea Wagner
We discuss the generalization of the point-to-point (and single-source) shortest path problem to instances where the shortest path must satisfy a formal language constraint. We describe theoretical...
04261 Abstracts Collection -- Algorithmic Methods for Railway Optimization (2006)
Kroon, Leo G., Wagner, Dorothea, Geraets, Frank, Zaroliagis, Christos
From 20.06.04 to 25.06.04, the Dagstuhl Seminar 04261 ``Algorithmic Methods for Railway Optimization'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During...
A Hybrid Model for Drawing Dynamic and Evolving Graphs (2006)
Gaertler, Marco, Wagner, Dorothea
Dynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative static view or...
05361 Abstracts Collection -- Algorithmic Aspects of Large and Complex Networks (2006)
Leonardi, Stefano, Wagner, Dorothea
From 04.09.05 to 09.09.05, the Dagstuhl Seminar 05361 ``Algorithmic Aspects of Large and Complex Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl....
Station Location - Complexity and Approximation (2006)
Mecke, Steffen, Schöbel, Anita, Wagner, Dorothea
We consider a geometric set covering problem. In its original form it consists of adding stations to an existing geometric transportation network so that each of a given set of settlements is not too...
06091 Executive Summary -- Data Structures (2006)
Arge, Lars, Sedgewick, Robert, Wagner, Dorothea
The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on data structures, including randomized, cache-oblivious and succinct data structures. There was some shift of interest...
06091 Abstracts Collection -- Data Structures (2006)
Arge, Lars, Sedgewick, Robert, Wagner, Dorothea
From 26.02.06 to 03.03.06, the Dagstuhl Seminar 06091 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...
Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles (2005)
Brandes, Ulrik, Cornelsen, Sabine, Wagner, Dorothea
A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut in the family is represented by a simple closed curve and vice versa. We show that the families of...
Drawing the as graph in 2.5 dimensions (2005)
Michael Baur, Ulrik Br, Marco Gaertler, Dorothea Wagner
Abstract. We propose a method for drawing AS graph data using 2.5D graph visualization. In order to bring out the pure graph structure of the AS graph we consider its core hierarchy. The k-cores are...
Approximating clustering coefficient and transitivity (2005)
Thomas Schank, Dorothea Wagner
Since its introduction in the year 1998 by Watts and Strogatz, the clustering coefficient has become a frequently used tool for analyzing graphs. In 2002 the transitivity was proposed by Newman,...
Engineering planar separator algorithms (2005)
Martin Holzer, Grigorios Prasinos, Frank Schulz, Dorothea Wagner, Christos Zaroliagis
Abstract. We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of the nodes whose removal separates the graph into two components of...
Automated drawings of metro maps (2005)
Betreuer Prof, Dorothea Wagner, Er Wolff, Martin Nöllenburg, ...
This diploma thesis investigates the problem of drawing metro maps which is defined as follows. Given a planar graph G of maximum degree 8 with its embedding and vertex locations (e.g. the physical...
04091 Abstracts Collection -- Data Structures (2005)
Albers, Susanne, Sedgewick, Robert, Wagner, Dorothea
From 22.02. to 27.02.2004, Dagstuhl Seminar "Data Structures" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented...
Brandes, Ulrik, Wagner, Dorothea
Das Thema Netzwerkvisualisierung umfasst alle Aspekte der Darstellung relationaler Strukturen. Die automatische Erzeugung von Netzwerkvisualisierungen hat wichtige Anwendungen nicht nur innerhalb der...
How to draw the minimum cuts of a planar graph (2004)
Brandes, Ulrik, Cornelsen, Sabine, Fieß, Christian, Wagner, Dorothea
We show how to utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a first approach the cactus is transformed into...
Generating Node Coordinates for Shortest-Path Computations in Transportation Networks (2004)
Brandes, Ulrik, Schulz, Frank, Wagner, Dorothea, Willhalm, Thomas
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such...
Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles (2004)
Brandes, Ulrik, Cornelsen, Sabine, Wagner, Dorothea
A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa. We show that the families of cuts that admit...
Geometric shortest path containers (2004)
Dorothea Wagner, Thomas Willhalm, Christos Zaroliagis
In this paper, we consider Dijkstra’s algorithm for the single source single target shortest path problem in large sparse graphs. The goal is to reduce the response time for on-line queries by...
Drawing the As Graph in 2.5 Dimensions (2004)
Baur, Michael, Brandes, Ulrik, Gaertler, Marco, Wagner, Dorothea
We propose a method for drawing AS graph data using 2.5D graph visualization. In order to bring out the pure graph structure of the AS graph we consider its core hierarchy. The k-cores are...
Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles (2004)
Ulrik Brandes, Sabine Cornelsen, Dorothea Wagner, ...
A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut in the family is represented by a simple closed curve and vice versa. We show that the families of...
Combining speed-up techniques for shortest-path computations (2004)
Martin Holzer, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Computing a shortest path from one node to another in a directed graph is a very common task in practice. This problem is classically solved by Dijkstra’s algorithm. Many techniques are known to...
Communicating centrality in policy network drawings (2003)
Brandes, Ulrik, Kenis, Patrick, Wagner, Dorothea
We introduce a network visualization technique that supports an analytical method applied in the social sciences. Policy network analysis is an approach to study policy making structures, processes,...
Two Approaches for Time-Table Information : a Comparison of Models and Performance (2003)
Pyrga, Evangelia, Schulz, Frank, Wagner, Dorothea, Zaroliagis, Christos
We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach every event at a station,...
Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs (2003)
Wagner, Dorothea, Willhalm, Thomas
In this paper, we consider Dijkstra's algorithm for the single source single target shortest paths problem in large sparse graphs. The goal is to reduce the response time for online queries by using...
Experiments on graph clustering algorithms (2003)
Ulrik Br, Marco Gaertler, Dorothea Wagner
Abstract. A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on...
visone - analysis and visualization of social networks (2003)
We describe visone, a tool that facilitates the visual exploration of social networks. Social network analysis is a methodological approach in the social sciences using graph-theoretic concepts to...
Experiments on graph clustering algorithms (2003)
Ulrik Br, Marco Gaertler, Dorothea Wagner
Abstract. A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on...
Experiments on Graph Clustering Algorithms (2003)
Ulrik Brandes, Marco Gaertler, Dorothea Wagner
A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on particular aspects...
Two Approaches for Time-Table Information: (2003)
Comparison Of Models, Evangelia Pyrga, Evangelia Pyrga, Frank Schulz, Frank Schulz, Dorothea Wagner, ...
We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach every event at a station,...
Experiments on Graph Clustering Algorithms (2003)
Brandes, Ulrik, Gaertler, Marco, Wagner, Dorothea
A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on particular aspects...
Dynamic Shortest Paths Containers (2003)
Dorothea Wagner, Thomas Willhalm, Christos Zaroliagis
Using a set of geometric containers to speed up shortest path queries in a weighted graph has been proven a useful tool for dealing with large sparse graphs. Given a layout of a graph G = (V, E), we...
Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs (2003)
Dorothea Wagner, Thomas Willhalm
In this paper, we consider Dijkstra's algorithm for the single source single target shortest paths problem in large sparse graphs. The goal is to reduce the response time for online queries by...
Geometric speed-up techniques for finding shortest paths in large sparse graphs (2003)
Dorothea Wagner, Thomas Willhalm, D. Wagner, T. Willhalm
In this paper, we consider Dijkstra’s algorithm for the single source single target shortest paths problem in large sparse graphs. The goal is to reduce the response time for online queries by...
Sketch-Driven Orthogonal Graph Drawing (2002)
Brandes, Ulrik, Eiglsperger, Markus, Kaufmann, Michael, Wagner, Dorothea
We present an orthogonal graph drawing algorithm that uses a sketchy drawing of the graph as input. While the algorithm produces an orthogonal drawing with few bends in the Kandinsky model it also...
Generating Node Coordinates for Shortest-Path Computations in Transportation Networks (2002)
Brandes, Ulrik, Schulz, Frank, Wagner, Dorothea, Willhalm, Thomas
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such...
Using multi-level graphs for timetable information in railway systems (2002)
Frank Schulz, Dorothea Wagner, Christos Zaroliagis
Abstract. In many fields of application, shortest path finding problems in very large graphs arise. Scenarios where large numbers of on-line queries for shortest paths have to be processed in...
Drawing graphs on two and three lines (2002)
Sabine Cornelsen, Thomas Schank, Dorothea Wagner
Abstract. We give a linear-time algorithm to decide whether a graph has a planar LL-drawing, i.e. a planar drawing on two parallel lines. This has previously been known only for trees. We utilize...
Drawing graphs on two and three lines (2002)
Sabine Cornelsen, Thomas Schank, Dorothea Wagner
We give a linear-time algorithm to decide whether a graph has a planar LL-drawing, i.e., a planar drawing on two parallel lines. We utilize this result to obtain planar drawings on three lines for a...
Exploratory Network Visualization : Simultaneous Display of Actor Status and Connections (2001)
Brandes, Ulrik, Raab, Jörg, Wagner, Dorothea
We propose a novel visualization approach that facilitates graphical exploration and communication of relative actor status in social networks. The main idea is to map, in a drawing of the entire...
How to Draw the Minimum Cuts of a Planar Graph (Extended Abstract) (2001)
Brandes, Ulrik, Cornelsen, Sabine, Wagner, Dorothea
We show how utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a first approach the cactus is transformed into a...
Planarity of the 2-level Cactus Model (2001)
Cornelsen, Sabine, Dinitz, Yefim, Wagner, Dorothea
The 2-level cactus introduced by Dinitz and Nutov (1995) is a data structure that represents the minimum and minimum+1 edge-cuts of an undirected connected multi-graph G in a compact way. In this...
Exploratory Network Visualization: Simultaneous Display of Actor Status and Connections (2001)
Ulrik Brandes, Jörg Raab, Dorothea Wagner
We propose a novel visualization approach that facilitates graphical exploration and communication of relative actor status in social networks. The main idea is to map, in a drawing of the entire...
Travel Planning With Self-Made Maps (2001)
Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such...
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (2000)
Brandes, Ulrik, Wagner, Dorothea
Given a graph G = (V, E) and two vertices s, t belong to V, s unequal to t, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph...
Using Graph Layout to Visualize Train Interconnection Data (2000)
Brandes, Ulrik, Wagner, Dorothea
We consider the problem of visualizing interconnections in railway systems. Given time tables from systems with thousands of trains, we are to visualize basic properties of the connection structure...
Dynamic WWW Structures in 3D (2000)
Brandes, Ulrik, Kääb, Vanessa, Löh, Andreas, Wagner, Dorothea, Willhalm, Thomas
We describe a method for three-dimensional straight-line representation of dynamic directed graphs (such as parts of the World Wide Web). It has been developed on the occasion of the 1998 Graph...
Recognizing Bundles in Time Table Graphs : a Structural Approach (2000)
Liebers, Annegret, Wagner, Dorothea, Weihe, Karsten
We are dealing with an application problem arising in a cooperation with the national German railway company which occurs in the analysis of time table data. The purpose is to infer the underlying...
Theoretische Grundlagen der Informatik : Skript zur Vorlesung vom WS 98/99 (2000)
Wagner, Dorothea, Gaertler, Marco, Handke, Dagmar
Vorlesungsausarbeitung der Vorlesung Theoretische Grundlagen der Informatik vom Wintersemester 1998/1999 an der Universität Konstanz.
Fully Dynamic Orthogonal Graph Layout for Interactive Systems (2000)
Brandes, Ulrik, Güdemann, Michael, Wagner, Dorothea
We combine and supplement existing approaches to arrive at a general algorithm for dynamic orthogonal graph drawing with few bends. Our approach is applicable to non-planar graphs with vertices of...
Fast Layout Methods for Timetable Graphs (2000)
Ulrik Brandes, Galina Shubina, Roberto Tamassia, Dorothea Wagner
Abstract. Timetable graphs are used to analyze transportation networks. In their visualization, vertex coordinates are xed to preserve the underlying geography, but due to small angles and overlaps,...
Dynamic www structures in 3d (2000)
Ulrik Brandes, Vanessa Kääb, Andres Löh, Dorothea Wagner, Thomas Willhalm
We describe a method for three-dimensional straight-line representation of dynamic directed graphs (such as parts of the World Wide Web). It has been developed on the occasion of the 1998 Graph...
Contextual visualization of actor status in social networks (2000)
Konstanzer Schriften, Mathematik Informatik, Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
We propose a novel information visualization approach for an analytical method applied in the social sciences. In social network analysis, social structures are formally represented as graphs, and...
Dynamic www structures in 3d (2000)
Ulrik Brandes, Vanessa Kaab, Andres Loh, Dorothea Wagner, Thomas Willhalm
We describe a method for three-dimensional straight-line representation of dynamic directed graphs (such as parts of the World Wide Web). It has been developed on the occasion of the 1998 Graph...
Fully Dynamic Orthogonal Graph Layout for Interactive Systems (2000)
Michael Güdemann, Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
. We combine and supplement existing approaches to arrive at a general algorithm for dynamic orthogonal graph drawing with few bends. Our approach is applicable to non-planar graphs with vertices of...
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport (2000)
Frank Schulz, Dorothea Wagner, Karsten Weihe
this paper, we consider a di#erent scenario: space consumption is not an issue, but the system has to answer a potentially infinite number of customer queries for optimal travel connections on--line....
Implementation of $O(nm \log n)$ weighted matchings: The power of data structures (2000)
Mehlhorn, Kurt, Schäfer, Guido, Näher, Stefan, Wagner, Dorothea
We describe the implementation of an $O(nm \log n)$ algorithm for weighted matchings in general graphs. The algorithm is a variant of the algorithm of Galil, Micali, and Gabow and requires the use of...
Explorations into the Visualization of Policy Networks (1999)
Brandes, Ulrik, Kenis, Patrick, Raab, Jörg, Schneider, Volker, Wagner, Dorothea
Visualization is an important aspect of both exploration and communication of categorical as well as relational data. Graphical displays of policy networks are particularly attractive, since they...
PlaNet : A Software Package of Algorithms and Heuristics on Planar Networks (1999)
Brandes, Ulrik, Neyer, Gabriele, Schickenrieder, Wolfram, Wagner, Dorothea, Weihe, Karsten
We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on...
Empirical Design of Geometric Algorithms (1999)
Weihe, Karsten, Brandes, Ulrik, Liebers, Annegret, Müller-Hannemann, Matthias, Wagner, Dorothea, Willhalm, Thomas
The computer--aided solution to algorithmic problems is becoming more and more important in various application domains. This is in particular true for computational geometry. For example, geometric...
Über das Zeichnen von Graphen (1999)
Brandes, Ulrik, Wagner, Dorothea
Zeichnungen sind nicht nur ein ansprechendes, sondern auch ein sehr effektives Mittel, um die durch einen Graphen repräasentierte Information zu vermitteln. Der geeignete Entwurf solcher Zeichnungen...
On the Hardness of Recognizing Bundles in Time Table Graphs (1999)
Annegret Liebers, Annegret Liebers, Dorothea Wagner, Dorothea Wagner, Karsten Weihe, Karsten Weihe
. Motivated by a problem arising in a cooperation with the national German railway company, we construct a directed graph from a set of train time tables where train stations correspond to vertices,...
Recognizing Bundles in Time Table Graphs: A Structural Approach (1999)
Annegret Liebers, Annegret Liebers, Dorothea Wagner, Dorothea Wagner, Karsten Weihe, Karsten Weihe
this paper is a directed graph constructed from train time tables, where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. Determining the...
On the Complexity of Partial Order Properties (1999)
Stefan Felsner, Ravi Kant, C. Pandu Rangan, Dorothea Wagner
The recognition complexity of ordered set properties is considered (in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property). We...
On the Hardness of Recognizing Bundles in Time Table Graphs (1999)
Annegret Liebers, Annegret Liebers, Dorothea Wagner, Dorothea Wagner, Karsten Weihe, Karsten Weihe
In a cooperation with the national German railway company, we construct a directed graph from a set of train time tables where train stations correspond to vertices, and where pairs of consecutive...
Empirical Design of Geometric Algorithms (1999)
Ulrik Brandes, Annegret Liebers, Matthias Müller-Hannemann, Dorothea Wagner, Karsten Weihe, Karsten Weihe, ...
this paper, we will discuss our experiences with a few obstacles that occurred in four of our projects and significantly influenced our reasoning on algorithms in each of them. These projects stem...
Centrality in Policy Network Drawings : (Extended Abstract) (1999)
Brandes, Ulrik, Kenis, Patrick, Wagner, Dorothea
We report on first results of a cooperation aiming at the usage of graph drawing techniques to convey domain-specific information contained in policy or, more general, social networks. Policy network...
Using Graph Layout to Visualize Train Inerconnection Data (1998)
Brandes, Ulrik, Wagner, Dorothea
We are concerned with the problem of visualizing interconnections in railroad systems. The real-world systems we have to deal with contain connections of thousands of trains. To visualize such a...
Explorations into the Visualization of Policy Networks (1998)
Brandes, Ulrik, Kenis, Patrick, Raab, Jörg, Schneider, Volker, Wagner, Dorothea
Visualization is an important aspect of both exploration and communication of categorical as well as relational data. Graphical displays of policy networks are particularly attractive, since they...
Dynamic Grid Embedding with Few Bends and Changes (1998)
Brandes, Ulrik, Wagner, Dorothea
In orthogonal graph drawing, edges are represented by sequences of horizontal and vertical straight line segments. For graphs of degree at most four, this can be achieved by embedding the graph in a...
Using Graph Layout to Visualize Train Interconnection Data (1998)
Ulrik Brandes, Dorothea Wagner
We consider the problem of visualizing interconnections in railway systems. Given time tables from systems with thousands of trains, we are to visualize basic properties of the connection structure...
Dynamic Grid Embedding with Few Bends and Changes (1998)
Ulrik Brandes, Dorothea Wagner
In orthogonal graph drawing, edges are represented by sequences of horizontal and vertical straight line segments. For graphs of degree at most four, this can be achieved by embedding the graph in a...
Using Graph Layout to Visualize Train Interconnection Data (1998)
Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
We are concerned with the problem of visualizing interconnections in railroad systems. The real-world systems we have to deal with contain connections of thousands of trains. To visualize such a...
Explorations into the Visualization of Policy Networks (1998)
J Org Raab, Ulrik Brandes, Ulrik Brandes, Patrick Kenis, Patrick Kenis, Jörg Raab, ...
Visualization is an important aspect of both exploration and communication of categorical as well as relational data. Graphical displays of policy networks are particularly attractive, since they...
Dieter Kratsch, Hoang-Oanh Le, Dieter Kratsch, Haiko Müller, Haiko M Uller, ...
A spanning tree of a graph is a k-additive tree spanner whenever the distance of every two vertices in the graph or in the tree differs by at most k. In this paper we show that certain classes of...
Using Graph Layout to Visualize Train Interconnection Data (1998)
Ulrik Brandes, Dorothea Wagner
We consider the problem of visualizing interconnections in railway systems. Given time tables from systems with thousands of trains, we are to visualize basic properties of the connection structure...
Dynamic Grid Embedding with Few Bends and Changes (1998)
Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
In orthogonal graph drawing, edges are represented by sequences of horizontal and vertical straight line segments. For graphs of degree at most four, this can be achieved by embedding the graph in a...
A Bayesian Paradigm for Dynamic Graph Layout (1997)
Brandes, Ulrik, Wagner, Dorothea
Dynamic graph layout refers to the layout of graphs that change over time. These changes are due to user interaction, algorithms, or other underlying processes determining the graph. Typically, users...
Brandes, Ulrik, Wagner, Dorothea
Given a graph G = (V, E) and two vertices s, t belong to V, s unequal to t, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph...
A Bayesian Paradigma for Dynamic Graph Layout (1997)
Brandes, Ulrik, Wagner, Dorothea
Dynamic graph layout refers to the layout of graphs that change over time. These changes are due to user interaction, algorithms, or other underlying processes determining the graph. Typically, users...
Random Field Models for Graph Layout (1997)
Brandes, Ulrik, Wagner, Dorothea
We propose a new framework for the layout of graphs, which both unifies and generalizes many approaches known from the literature. Doing so, we briefly survey a number of models, particularly...
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (1997)
Brandes, Ulrik, Wagner, Dorothea
Given a graph G=(V,E) and two different vertices s,t in V, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph is directed or...
A Bayesian paradigma for dynamic graph layout (1997)
Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
Dynamic graph layout refers to the layout of graphs that change over time. These changes are due to user interaction, algorithms, or other underlying processes determining the graph. Typically, users...
Random field models for graph layout (1997)
Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
We propose a new framework for the layout of graphs, which both unifies and generalizes many approaches known from the literature. Doing so, we briefly survey a number of models, particularly...
A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (1997)
Ulrik Brandes, Ulrik Brandes, Dorothea Wagner, Dorothea Wagner
Given a graph G = (V; E) and two vertices s; t 2 V, s 6 = t, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph is directed or...
The Vertex-Disjoint Menger Problem In Planar Graphs (1997)
Heike Ripphausen-lipa, Dorothea Wagner, Karsten Weihe
. We consider the problem of finding a maximum collection of vertex-disjoint paths in undirected, planar graphs from a vertex s to a vertex t. This problem is usually solved using flow techniques,...
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (1997)
Ulrik Brandes, Dorothea Wagner
Abstract. Given a graph G = (V; E) and two vertices s; t 2 V , s 6= t, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph is...
Wiring Edge-Disjoint Layouts (1996)
Kuchem, Ruth, Wagner, Dorothea
We consider the wiring or layer assignment problem for edge-disjoint layouts. The wiring problem is well understood for the case that the underlying layout graph is a square grid. Nothing is known so...
Edge-Disjoint Paths in Planar Graphs with Short Total Length (1996)
Brandes, Ulrik, Neyer, Gabriele, Wagner, Dorothea
The problem of finding edge-disjoint paths in a planar graph such that each path connects two specified vertices on the outer face of the graph is well studied. The "classical" Eulerian case...
D.: Edge-disjoint paths in planar graphs with short total length (1996)
Ulrik Brandes, Ulrik Brandes, Gabriele Neyer, Gabriele Neyer, Dorothea Wagner, Dorothea Wagner
The problem of finding edge--disjoint paths in a planar graph such that each path connects two specified vertices on the outer face of the graph is well studied. The "classical "...
Paul Molitor, Uwe Sparmann, Dorothea Wagner
We examine the constrained via minimization problem with pin preassignments (CVMPP) which arises in connection with hierarchical physical synthesis. Let A be a circuit composed of subcircuits B, C,...
Jahresbericht 1994 bis 1996 Informatik - Universität Konstanz (1994)
Herausgegeben Marc, Dorothea Wagner (eds.), Marc H. Scholl, Dorothea Wagner
in EATCS Bulletin, June 1995, pages 332--333. [Wei95] Karsten Weihe. Besprechung von R.K. Ahuja, T.L. Magnanti, J.B. Orlin: `Network Flows', Prentice Hall, 1993. Zeitschrift f ur Operations...
On the Complexity of Partial Order Properties (1993)
Stefan Felsner, Dorothea Wagner
The recognition complexity of ordered set properties is considered, i.e. how many questions have to be asked to decide if an unknown ordered set has a prescribed property. We prove a lower bound of...
An Animated Library of Combinatorial VLSI--Routing Algorithms (1993)
Dorothea Wagner, Dorothea Wagner, Karsten Weihe, Karsten Weihe
We present a library, CRoP, of combinatorial algorithms for routing problems that occur during the design process of integrated circuits. Most of them are really sophisticated theoretical algorithms,...
Linear-Time Algorithms for Disjoint Two-Face Paths Problems in Planar Graphs (1993)
Heike Ripphausen-Lipa, Dorothea Wagner, Dorothea Wagner, Karsten Weihe, Karsten Weihe
In this paper we present a linear-time algorithm for the vertex-disjoint Two-Face Paths Problem in planar graphs, i.e., the problem of finding k vertex-disjoint paths between pairs of terminals which...
Paul Molitor, Uwe Sparmann, Dorothea Wagner
We examine the constrained via minimization problem with pin preassignments (CVMPP) which arises in connection with hierarchical physical synthesis. Let A be a circuit composed of subcircuits B, C,...
An Animated Library of Combinatorial VLSI-Routing Algorithms (1993)
Dorothea Wagner, Karsten Weihe
nt phase and specifies the courses of the wires through the grid (lay- out). More precisely, the layout is only the first step. In This research was supported by the Technische Universitat Berlin...
Simple Algorithms for Steiner Trees and Paths Packing Problems in Planar Graphs (1993)
In this paper we give a short survey on efficient algorithms for Steiner trees and paths packing problems in planar graphs. We particularly concentrate on recent results. The first result is a...
An Animated Library of Combinatorial VLSI-Routing Algorithms (1993)
Dorothea Wagner, Karsten Weihe
We present a library, CRoP, of combinatorial algorithms for routing problems that occur during the design process of integrated circuits. Most of them are really sophisticated theoretical algorithms,...
Rolf H. Möhring, Dorothea Wagner, Frank Wagner, Frank Wagner
This article gives a survey on the interaction between integrated circuit layout and combinatorial optimization. The viewpoint taken is that of a combinatorialist, which means that main emphasis is...
Between Min Cut and Graph Bisection (1991)
Dorothea Wagner, Dorothea Wagner, Frank Wagner, Frank Wagner
. We investigate a class of graph partitioning problems whose two extreme representatives are the well-known Min Cut and Graph Bisection problems. The former is known to be efficiently solvable by...
A New Approach to Knock-Knee Channel Routing (1991)
Dorothea Wagner, Dorothea Wagner
We present a new channel routing algorithm in the knock-knee mode that produces for dense problems area-optimal layouts with minimum total wire length and O(n) bends (n number of nets), where the...
Diplomarb. der Vereinigung Schweizerischer Bibliothekare, Bern.
Contextual Visualization of Actor Status in Social Networks
Ulrik Brandes, Dorothea Wagner
We propose a novel information visualization approach for an analytical method applied in the social sciences. In social network analysis, social structures are formally represented as graphs, and...
THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
ANITA SCHöBEL, HORST W. HAMACHER, ANNEGRET LIEBERS, DOROTHEA WAGNER
In this paper we consider the location of stops along the edges of an already existing public transportation network. This can be the introduction of bus stops along some given bus routes, or of...