Ulrik Brandes

Attributes • Complex Types (2008)

My first memory of the subject of this thesis is my own ignorance. In September 1995, Dorothea Wagner had arranged for the newer members of her working group to attend a symposium held in Passau. The...

Ulrik Brandes, Markus Eiglsperger, Zuehlke Engineering Ag, Juergen Lerner, Christian Pich

GraBaTs’04 Preliminary Version GXL to GraphML and Vice Versa with XSLT 1 Abstract (2008)

Ulrik Brandes, Jürgen Lerner, Christian Pich

We explore the issues involved in converting graph data stored in GXL or GraphML into each other. It turns out that XSLT provides a simple, portable, and effective mechanism for format conversion in...

On Variants of Shortest-Path Betweenness Centrality and their Generic Computation 1 (2008)

Engineering Graph Clustering: Models and Experimental Evaluation (2008)

Betweenness centrality based on shortest paths is a standard measure of control utilized in numerous studies and implemented in all relevant software tools for network analysis. In this paper, a...

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...

Dynamic Spectral Layout with an Application to Small Worlds (2008)

Ulrik Brandes, Daniel Fleischer

Spectral methods are naturally suited for dynamic graph layout because, usually, moderate changes of a graph yield moderate changes of the layout. We discuss some general principles for dynamic graph...

ABSTRACT Visual Statistics for Collections of Clustered Graphs (2008)

Ulrik Brandes, Jürgen Lerner, Miranda J. Lubbers, Chris Mccarty, José Luis Molina

We propose a method to visually summarize collections of networks on which a clustering of the vertices is given. Our method allows for efficient comparison of individual networks, as well as for...

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...

Eager st-Ordering (2008)

Generating Node Coordinates for Shortest-Path Computations in Transportation Networks (2008)

Abstract. Given a biconnected graph G =(V,E) withedge{s, t} ∈E, an st-ordering is an ordering v1,...,vn of V such that s = v1, t = vn, and every other vertex has both a higher-numbered and a...

Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm

this paper deals only with speed-up techniques that assure the correctness of the result

Visual analysis of controversy in user-generated encyclopedias (2008)

On Modularity Clustering (2008)

Wikipedia is a large and rapidly growing Web-based collaborative authoring environment,wher e anyone on the Internet can create,modify ,and delete pages about encyclopedic topics. A remarkable...

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...

On Variants of Shortest-Path Betweenness Centrality and their Generic Computation (2008)

Visualizing Internet Evolution on the Autonomous Systems Level (2008)

Betweenness centrality based on shortest paths is a standard measure of control utilized in numerous studies and implemented in all relevant software tools for network analysis. In this paper, a...

Boitmanis, Krists, Brandes, Ulrik, Pich, Christian

We propose a visualization approach for large dynamic graph structures with high degree variation and low diameter. In particular, we reduce visual complexity by multiple modes of representation in a...

Visual Statistics for Collections of Clustered Graphs (2008)

Brandes, Ulrik, Lerner, Jürgen, Lubbers, Miranda J., McCarty, Chris, Molina, Jose Luis

We propose a method to visually summarize collections of networks on which a clustering of the vertices is given. Our method allows for efficient comparison of individual networks, as well as for...

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...

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...

c Fachbereich Mathematik und Statistik (2007)

Eager St-ordering, Ulrik Brandes, Ulrik Brandes

Abstract. Given a biconnected graph G = (V; E) and an edge fs; tg 2 E, an st-ordering is an ordering v1; : : : ; vn of V such that s = v1, t = vn, and every other vertex has both a higher-numbered...

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...

Visual Understanding of Metabolic Pathways across Organisms Using Layout in Two and a Half Dimensions (2007)

Ulrik Brandes, Tim Dwyer, Falk Schreiber

this paper we are interested in visualizing several related metabolic pathways in such a way that the inherent di#erences can be explored by trained biologists in order to understand the evolutionary...

2 (2007)

Franz Brandenburg, Ulrik Brandes, Michael Himsolt, Marcus Raitner, Daimlerchrysler Forschungszentrum Ulm

3

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...

Dynamic Spectral Layout with an Application to Small Worlds (2007)

Brandes, Ulrik, Fleischer, Daniel, Puppe, Thomas

Spectral methods are naturally suited for dynamic graph layout because, usually, moderate changes of a graph yield moderate changes of the layout. We discuss some general principles for dynamic graph...

Centrality Estimation in Large Networks (2007)

Brandes, Ulrik, Pich, Christian

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves...

Eigensolver Methods for Progressive Multidimensional Scaling of Large Data (2007)

Brandes, Ulrik, Pich, Christian

We present a novel sampling-based approximation technique for classical multidimensional scaling that yields an extremely fast layout algorithm suitable even for very large graphs. It produces...

Colored Simultaneous Geometric Embeddings (2007)

Brandes, Ulrik, Erten, Cesim, Fowler, J. Joseph, Frati, Fabrizio, Geyer, Markus, Gutwenger, Carsten, ...

We introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of...

Revision and Co-revision in Wikipedia : Detecting Clusters of Interest (2007)

Role-equivalent Actors in Networks : Group Structures Beyond Dense Communities (2007)

The online encyclopedia Wikipedia gives rise to a multitude of network structures such as the citation network of its pages or the coauthorship network of users. In this paper we analyze another...

C.: Centrality estimation in large networks (2007)

Communities in social networks are often defined as groups of densely connected actors. However, members of the same dense group are not equal but may differ largely in their social position or in...

Ulrik Brandes, Christian Pich

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves...

i (2007)

Fachbereich Informatik Und Informationswissenschaft, Martin Hoefer, Prof Dr, Ulrik Brandes, Prof Dr, ...

ii

Visual Analysis of Controversy in User-generated Encyclopedias (2007)

Multi-circular Layout of Micro/Macro Graphs (2007)

Wikipedia is a large and rapidly growing Web-based collaborative authoring environment, where anyone on the Internet can create, modify, and delete pages about encyclopedic topics. A remarkable...

Baur, Michael, Brandes, Ulrik

We propose a layout algorithm for micro/macro graphs, i.e. relational structures with two levels of detail. While the micro-level graph is given, the macro-level graph is induced by a given partition...

Correspondence: (2007)

Ulrik Brandes, Jürgen Lerner, Jürgen Lerner

www.palgrave-journals.com/ivs Visual analysis of controversy in user-generated encyclopedias �

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...

Geographic Routing on Improved Coordinates (2007)

Brandes, Ulrik, Fleischer, Daniel

We consider routing methods for networks when geographic positions of nodes are available. Instead of using the original geographic coordinates, however, we precompute virtual coordinates using...

Explanation Through Network Visualization (2006)

Brandes, Ulrik, Kenis, Patrick, Raab, Jörg

Assessments of configurations, dynamics, and cause and effect are at the heart of our thinking and explanation. Although numerous methods for such assessments have been developed and are being used...

Summarizing Dynamic Bipolar Conflict Structures (2006)

Brandes, Ulrik, Fleischer, Daniel, Lerner, Jürgen

We present a method for visual summary of bilateral conflict structures embodied in event data. Such data consists of actors linked by time-stamped events, and may be extracted from various sources...

Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities (2006)

Angle and Distance Constraints on Tree Drawings (2006)

Random 3-colorable graphs that are generated according to a G(n, p)-like model can be colored optimally, if p ≥ c/n for some large constant c. However, these methods fail in a model where the...

Brandes, Ulrik, Schlieper, Barbara

We consider planar drawings of trees that must satisfy constraints on the angles between edges incident to a common vertex and on the distances between adjacent vertices. These requirements arise...

Affiliation Dynamics with an Application to Movie-Actor Biographies (2006)

Brandes, Ulrik, Hoefer, Martin, Pich, Christian

We propose a visualization approach for dynamic affiliation networks in which events are characterized by a set of descriptors. It uses a radial ripple metaphor to display the passing of time and...

WordSpace Visual Summary of Text Corpora (2006)

Brandes, Ulrik, Hoefer, Martin, Lerner, Jürgen

In recent years several well-known approaches to visualize the topical structure of a document collection have been proposed. Most of them feature spectral analysis of a term-document matrix with...

Efficient Generation of Large Random Networks (2005)

Batagelj, Vladimir, Brandes, Ulrik

Random networks are frequently generated, for example, to investigate the effects of model parameters on network properties or to test the performance of algorithms. Recent interest in statistics of...

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...

Dynamic Spectral Layout of Small Worlds (2005)

Brandes, Ulrik, Fleischer, Daniel, Puppe, Thomas

Spectral methods are naturally suited for dynamic graph layout, because moderate changes of a graph yield moderate changes of the layout under weak assumptions. We discuss some general principles for...

Drawing Phylogenetic Trees : (Extended Abstract) (2005)

Bachmaier, Christian, Brandes, Ulrik, Schlieper, Barbara

We present linear-time algorithms for drawing phylogenetic trees in radial and circular representations. In radial drawings given edge lengths (representing evolutionary distances) are preserved, but...

Centrality Measures Based on Current Flow (2005)

Brandes, Ulrik, Fleischer, Daniel

We consider variations of two well-known centrality measures, betweenness and closeness, witha different model of information spread. Rather than along shortest paths only, it is assumed that...

Highlighting Conflict Dynamics in Event Data (2005)

Brandes, Ulrik, Fleischer, Daniel, Lerner, Jürgen

We present a method for visual summary of bilateral conflict structures embodied in event data. Such data consists of actors linked by time-stamped events, and may be extracted from various sources...

Netzwerkvisualisierung (2004)

How to draw the minimum cuts of a planar graph (2004)

Das Thema Netzwerkvisualisierung umfasst alle Aspekte der Darstellung relationaler Strukturen. Die automatische Erzeugung von Netzwerkvisualisierungen hat wichtige Anwendungen nicht nur innerhalb der...

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...

Visual Understanding of Metabolic Pathways Across Organisms using Layout in Two and a Half Dimensions (2004)

Brandes, Ulrik, Dwyer, Tim, Schreiber, Falk

We propose a method for visualizing a set of related metabolic pathways across organisms using 2 1/2 dimensional graph visualization. Interdependent,two-dimensional layouts of each pathway are...

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...

Crossing Reduction in Circular Layouts (2004)

Baur, Michael, Brandes, Ulrik

We propose a two-phase heuristic for crossing reduction in circular layouts. While the first algorithm uses a greedy policy to build a good initial layout, an adaptation of the sifting heuristic for...

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...

GraphML Transformation (2004)

Brandes, Ulrik, Pich, Christian

The efforts put into XML-related technologies have exciting consequences for XML-based graph data formats such as GraphML. We here give a systematic overview of the possibilities offered by XSLT...

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...

Visual Triangulation of Network-Based Phylogenetic Trees (2004)

Brandes, Ulrik, Dwyer, Tim, Schreiber, Falk

Phylogenetic trees are built by examining differences in the biological traits of a set of species. An example of such a trait is a biological network such as a metabolic pathway, common to all...

Brandes, Ulrik, Dwyer, Tim, Schreiber, Falk

We propose a method for visualizing a set of related metabolic pathways using 2 1/2D graph drawing. Interdependent, twodimensional layouts of each pathway are stacked on top of each other so that...

Graph Drawing Contest Report (2004)

Standard methods for role assignment partition the vertex set of a graph in such a way that vertices in the same class can be considered to have equivalent roles in the graph. Several classes of...

Brandenburg, Franz J., Brandes, Ulrik, Eades, Peter, Marks, Joe

This report describes the Tenth Annual Graph Drawing Contest, held in conjunction with the 2003 Graph Drawing Symposium in Perugia, Italy. The purpose of the contest is to monitor and challenge the...

GXL to GraphML and Vice Versa with XSLT (2004)

Brandes, Ulrik, Lerner, Jürgen, Pich, Christian

We explore the issues involved in converting graph data stored in GXL or GraphML into each other. It turns out that XSLT provides a simple, portable, and effective mechanism for format conversion in...

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,...

Visual Ranking of Link Structures (2003)

Brandes, Ulrik, Cornelsen, Sabine

Methods for ranking World Wide Web resources according to their position in the link structure of the Web are receiving considerable attention, because they provide the first effective means for...

Visual unrolling of network evolution and the analysis of dynamic discourse (2003)

Brandes, Ulrik, Corman, Steven R.

We introduce a method for visualizing evolving networks. In addition to the intermediate states of the network, it conveys the nature of change between states by unrolling the dynamics of the...

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...

Visual Ranking of Link Structures (2003)

Ulrik Brandes, Sabine Cornelsen

Methods for ranking World Wide Web resources according to their position in the link structure of the Web are receiving considerable attention, because they provide the first e#ective means for...

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...

Eager st-Ordering (2002)

Fast and Simple Horizontal Coordinate Assignment (2002)

Given a biconnected graph G = (V,E) with edge {s, t} gehört E, an st-ordering is an ordering v1, . . .

Brandes, Ulrik, Köpf, Boris

We present a simple, linear-time algorithm to determine horizontal coordinates in layered layouts subject to a given ordering within each layer. The algorithm is easy to implement and compares well...

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...

Visualization of Bibliographic Networks with a Reshaped Landscape Metaphor (2002)

Brandes, Ulrik, Willhalm, Thomas

We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark...

Eager st-Ordering (2002)

Visualization of bibliographic networks with a reshaped landscape metaphor (2002)

Given a biconnected graph G=(V, E) and an edge {s,t} in E, an st-ordering is an ordering v1,...,vn of V such that s=v1, t=vn, and every other vertex has both a higher-numbered and a lower-numbered...

Ulrik Brandes, Thomas Willhalm, Fachbereich Informatik Und Informationswissenschaft, U. Br, T. Willhalm

We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark...

GraphML Progress Report - Structural Layer Proposal (2002)

Ulrik Brandes, Markus Eiglsperger, Ivan Herman, Michael Himsolt, M. Scott Marshall

Following a workshop on graph data formats held with the 8th Symposium on Graph Drawing (GD 2000), a task group was formed to propose a format for graphs and graph drawings that meets current and...

Eager st-Ordering (2002)

Abstract Visualization of Bibliographic Networks with a Reshaped Landscape Metaphor (2002)

Given a biconnected graph G = (V; E) with edge fs; tg 2 E, an st-ordering is an ordering v1 ; : : : ; vn of V such that s = v1 , t = vn , and every other vertex has both a higher-numbered and a...

Ulrik Brandes, Thomas Willhalm, U. Br, T. Willhalm

We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark...

c ○ Fachbereich Mathematik und Statistik (2002)

Ulrik Brandes, Eager St-ordering, Ulrik Brandes

Abstract. Given a biconnected graph G = (V, E) and an edge {s, t} ∈ E, an st-ordering is an ordering v1,..., vn of V such that s = v1, t = vn, and every other vertex has both a higher-numbered and...

Visual Unrolling of Network Evolution and the Analysis of Dynamic Discourse (2002)

Brandes, Ulrik, Corman, Steven R.

A new method for visualizing the class of incrementally evolving networks is presented. In addition to the intermediate states of the network it conveys the nature of the change between them by...

A Faster Algorithm for Betweenness Centrality (2001)

Exploratory Network Visualization : Simultaneous Display of Actor Status and Connections (2001)

The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require Theta(n3) time and Theta(n2) space, where n is...

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...

Visual Ranking of Link Structures (Extended Abstract) (2001)

Brandes, Ulrik, Cornelsen, Sabine

Methods for ranking World Wide Web resources according to their position in the link structure of the Web are receiving considerable attention, because they provide the first effective means for...

A faster algorithm for betweenness centrality (2001)

Exploratory Network Visualization: Simultaneous Display of Actor Status and Connections (2001)

The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require Θ(n 3) time and Θ(n 2) space, where n is the...

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...

Drawing on Physical Analogies (2001)

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (2000)

in Sections 4.2 and 4.3. An asset of physical modeling that is often overlooked is its inherent exibility. For this reason, we conclude this chapter by listing examples of model speci cations...

Using Graph Layout to Visualize Train Interconnection Data (2000)

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...

Dynamic WWW Structures in 3D (2000)

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...

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...

Faster Evaluation of Shortest-Path Based Centrality Indices (2000)

Fully Dynamic Orthogonal Graph Layout for Interactive Systems (2000)

Centrality indices are an important tool in network analysis, and many of them are derived from the set of all shortest paths of the underlying graph. The so-called betweenness centrality index is...

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...

Faster Evaluation of Shortest-Path Based Centrality Indices (2000)

Ulrik Brandes, Ulrik Brandes

Centrality indices are an important tool in network analysis, and many of them are derived from the set of all shortest paths of the underlying graph. The so-called betweenness centrality index is...

Graph Data Format Workshop Report (2000)

Brandes, Ulrik, Marshall, M. Scott, North, Stephen C.

Prompted by the increasing demand for a standard exchange format for graph data, an informal workshop was held in conjunction with Graph Drawing 2000. The participants identified requirements for...

Improving Angular Resolution in Visualizations of Geographic Networks (2000)

Brandes, Ulrik, Shubina, Galina, Tamassia, Roberto

In visualizations of large-scale transportation and communications networks, node coordinates are usually fixed to preserve the underlying geography, while links are represented as geodesics for...

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...

Layout of Graph Visualizations (1999)

Über das Zeichnen von Graphen (1999)

Visualisierung ist ein attraktives und effektives Mittel sowohl der Präsentation als auch der Exploration von Daten. In beiden Fällen ist das oberste Ziel die getreue Darstellung der durch die...

Graph Drawing Contest Report (1999)

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...

Franz J. Brandenburg, Franz J. Br, Ulrik Brandes, Peter Eades, Joe Marks

This report describes the Tenth Annual Graph Drawing Contest, held in conjunction with the 2003 Graph Drawing Symposium in Perugia, Italy. The purpose of the contest is to monitor and challenge the...

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...

Hunting Down Graph B (1999)

Einführung in den Umgang mit den Sun-Workstations im Informatik-Lehre-Pool G 228 bis G 230 an der Universität Konstanz : Revised Version (1998)

Graph B, the "Theory Graph", of the 1999 Graph Drawing Contest is visually explored using available and some hand-written graph drawing software.

Brandes, Ulrik, Liebers, Annegret

Using Graph Layout to Visualize Train Inerconnection Data (1998)

Explorations into the Visualization of Policy Networks (1998)

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...

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)

NP-Completeness Results for Minimum Planar Spanners (1998)

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...

Ulrik Brandes, Ulrik Brandes, Dagmar Handke, Dagmar Handke

Fakultat fur Mathematik und Informatik For any fixed parameter t 1, a t--spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their...

Using Graph Layout to Visualize Train Interconnection Data (1998)

NP-Completeness Results for Minimum Planar Spanners (1998)

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...

Ulrik Brandes, Dagmar Handke

this paper, we prove the

Dynamic Grid Embedding with Few Bends and Changes (1998)

NP-Completeness Results for Minimum Planar Spanners (1998)

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...

Ulrik Brandes, Dagmar Handke, Dagmar H

this paper, we prove the NP--hardness of finding minimum t--spanners for planar weighted graphs and digraphs if t 3, and for planar unweighted graphs and digraphs if t 5. We thus extend results on...

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...

Using Graph Layout to Visualize Train Interconnection Data (1998)

Dynamic Grid Embedding with Few Bends and Changes (1998)

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...

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...

NP-Completeness Results for Minimum Planar Spanners (1998)

Ulrik Brandes, Dagmar Handke

For any fixed parameter t greater or equal to 1, a t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G. A minimum...

A Bayesian Paradigm for Dynamic Graph Layout (1997)

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (Extended Abstract) (1997)

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...

A Bayesian Paradigma for Dynamic Graph Layout (1997)

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...

Random Field Models for Graph Layout (1997)

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...

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (1997)

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 Bayesian paradigma for dynamic graph layout (1997)

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...

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...

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs (1997)

NP-Completeness Results for Minimum Planar Spanners (1996)

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...

Brandes, Ulrik, Handke, Dagmar

For any fixed parameter t>=1, a t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G. A minimum t-spanner is a...

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 "...

Markoff-Felder als Hilfsmittel der Bildverarbeitung (1994)

Contextual Visualization of Actor Status in Social Networks

Gegenstand dieser Arbeit ist ein stochastisches Modell für digitalisierte und quantisierte (endliche) Bilddaten. Es soll gezeigt werden, dass die Bildbeschreibung durch Markoff-Felder ein...