Graph Algorithms and Applications 3

The following sections are included:

• Preface

• Journal of Graph Algorithms and Applications

• Contents

The following sections are included:

• A Few Words about the Conference

• A Few Words about the Papers

We prove that every triangle-free planar graph is the intersection graph of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and oblique) and in such a way that no two segments cross, i.e., intersect in a common interior point. This particular class of intersection graphs is also known as contact graphs.

We address in this paper the problem of constructing embeddings of planar graphs satisfying declarative, user-defined topological constraints. The constraints consist each of a cycle of the given graph and a set of its edges to be embedded inside this cycle and a set of its edges to be embedded outside this cycle. Their practical importance in graph visualization applications is due to the capability of supporting the semantics of graphs. Additionally, embedding algorithms for planar graphs with topological constraints can be combined with planar graph drawing algorithms that transform a given embedding into a topology preserving drawing according to particular drawing conventions and aesthetic criteria.

We obtain the following main results on the planarity problem with topological constraints. Since it turns out to be NP-complete, we develop a polynomial time algorithm for reducing the problem for arbitrary planar graphs to a planarity problem with constraints for biconnected graphs. This allows focussing on biconnected graphs when searching for heuristics or polynomial time subproblems. We then define a particular subproblem by restricting the maximum number of vertices that any two distinct cycles involved in the constraints can have in common. Whereas the problem remains NP-complete if this number exceeds 1, it can otherwise be solved in polynomial time. The embedding algorithm we develop for this purpose is based on the reduction method.

A level graph G = (V,E,ø) is a directed acyclic graph with a mapping ø : V → {1,2,…,k}, k ≥ 1 that partitions the vertex set V as V = V¹∪V²∪ … ∪V^k, V^j = ø⁻¹(j), Vⁱ∩V^j = ø for i ≠ j, such that ø(v) ≥ ø(u) + 1 for each edge (u,v) ∈ E. The level planarity testing problem is to decide if G can be drawn in the plane such that for each level Vⁱ, all v ∈ Vⁱ are drawn on the line l_i = {(x, k − i) | x ∈ ℝ}, the edges are drawn monotonically with respect to the vertical direction, and no edges intersect except at their end vertices.

In order to draw a level planar graph without edge crossings, a level planar embedding of the level graph has to be computed. Level planar embeddings are characterized by linear orderings of the vertices in each Vⁱ (1 ≤ i ≤ k). We present an time algorithm for embedding level planar graphs. This approach is based on a level planarity test by Junger, Leipert, and Mutzel (1998).

The existing literature gives efficient algorithms for mapping trees or less restrictively outerplanar graphs on a given set of points in a plane, so that the edges are drawn planar and as straight lines. We relax the latter requirement and allow very few bends on each edge while considering general plane graphs. Our results show two algorithms for mapping four-connected plane graphs with at most one bend per edge and for mapping general plane graphs with at most two bends per edge. Furthermore we give a point set, where for arbitrary plane graphs it is NP-complete to decide whether there is an mapping such that each edge has at most one bend.

The following sections are included:

• Introduction

• Three Easy Problems

• Openings

• Archaeology of Aesthetic

• On Invariants for Graph Drawing

• Hereditary Combinatorial Entropy of a Drawing

• Constructible World

• References

We prove a very general representation theorem for posets and, as a corollary, deduce that any abstract simplicial complex has a geometric realization in the Euclidean space of dimension dim P(Δ) − 1, where dim P(Δ) is the Dushnik-Miller dimension of the face order of Δ.

The paper describes two algorithms for threading unknown, finite directed Eulerian mazes. Each of these algorithms is performed by a traveling robot whose control is a finite-state automaton. It is assumed that each vertex has a circular list of its outgoing edges. The items of this list sure called exits. Each of the algorithms puts in one of the exits of each vertex a scan pebble. These pebbles can be used by a simple robot as traffic signals, which allow it to traverse an Eulerian cycle of the maze.

For a directed graph (maze) G(V, E), the simple algorithm performs O(|V|·|E|) edge traversals, while the advanced algorithm traverses every edge three times. Let d_out(v) be the out-degree of vertex v. The algorithms use, at each vertex v, a local memory of size O(log d_out(v)).

It is becoming a nice tradition and add-on to the Symposium on Graph Drawing to invite a selection of papers to be included in a special issue of Journal of Graph Algorithms and Applications. After a more theory-oriented special issue for GD'99, I decided to emphasize application-oriented papers…

We present a multi-scale layout algorithm for the aesthetic drawing of undirected graphs with straight-line edges. The algorithm is extremely fast, and is capable of drawing graphs that are substantially larger than those we have encountered in prior work. For example, the paper contains a drawing of a graph with over 15,000 vertices. Also we achieve “nice” drawings of 1000 vertex graphs in about 1 second. The proposed algorithm embodies a new multi-scale scheme for drawing graphs, which was motivated by the earlier multi-scale algorithm of Hadany and Harel [HH99]. In principle, it could significantly improve the speed of essentially any force-directed method (regardless of that method's ability of drawing weighted graphs or the continuity of its cost-function).

This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. The system is designed for drawing large graphs and uses a novel multi-dimensional force-directed method together with fast energy function minimization. The algorithm underlying the system employs a simple recursive coarsening scheme. Rather than being placed at random, vertices are placed intelligently, several at a time, at locations close to their final positions. The running time and space complexity of the system are near linear. The implementation is in C using OpenGL for 3D viewing. The GRIP system allows for drawing graphs with tens of thousands of vertices in under one minute on a mid-range PC. To the best of the authors' knowledge, GRIP surpasses the fastest previous algorithms. However, speed is not achieved at the expense of quality as the resulting drawings are quite aesthetically pleasing.

The need for a similarity measure for comparing two drawings of graphs arises in problems such as interactive graph drawing and the indexing or browsing of large sets of graphs. Many applications have been based on intuitive ideas of what makes two drawings look similar — for example, the idea that vertex positions should not change much. In this paper, we formally define several of these intuitive ideas of similarity and present the results of a user study designed to evaluate how well these measures reflect human perception of similarity.

The merit of automatic graph layout algorithms is typically judged by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising orthogonality). Experiments investigating the worth of such algorithms from the point of view of human usability can take different forms, depending on whether the graph has meaning in the real world, the nature of the usability measurement, and the effect being investigated (algorithms or aesthetics). Previous studies have investigated performance on abstract graphs with respect to both aesthetics and algorithms, finding support for reducing the number of crossings and bends, and increasing the display of symmetry.

This paper reports on preference experiments assessing the effect of individual aesthetics in the application domain of UML diagrams. Subjects' preferences for one diagram over another were collected as quantitative data. Their stated reasons for their choice were collected as qualitative data. Analysis of this data enabled us to produce a priority listing of aesthetics for this domain. These UML preference results reveal a difference in aesthetic priority from those of previous domain-independent experiments.

HERMES is a system for exploring and visualizing the Internet structure at the level of the Autonomous Systems and their interconnections. It relies on a three-tier architecture, on a large repository of routing information coming from heterogeneous sources, and on sophisticated graph drawing engine. Such an engine exploits static and dynamic graph drawing techniques, specifically devised for the visualization of large graphs with high density.

We present a framework for the automatic generation of layouts of statechart diagrams. Statecharts [16] are widely used for the requirements specification of reactive systems. Our framework is based on several techniques that include hierarchical drawing, labeling, and floorplanning, designed to work in a cooperative environment. Therefore, the resulting drawings enjoy several important properties: they emphasize the natural hierarchical decomposition of states into substates; they have a low number of edge crossings; they have good aspect ratio; and require a small area. We also present techniques for interactive operations. We have implemented our framework and obtained drawings for several statechart examples.

Enabling the user of a graph drawing system to preserve the mental map between two different layouts of a graph is a major problem. In this paper we present methods that smoothly transform one drawing of a graph into another without any restrictions to the class of graphs or type of layout algorithm.

This paper introduces a special graph family, together with an extensive characterization of some of its properties and two of its immediate applications. The graph denoted by T_i,j, is a regular hexavalent toroidal graph. The topological features of T_i,j include vertex symmetry, Hamiltonian decomposition, translation and rotation isomorphism. Topologically, the graph is a torus, while algebraically, it can also be expressed as a Cayley graph, defined on the cyclic group <1, k, k², −1, −k, −k²>, where k can be determined from the (i,j) parameters defining graph T_i,j. As a direct consequence, the proposed graph, which has ρ_i,j = i² + i · j + j² = (i + j)² − i · j vertices, is vertex-symmetric. For the special case when i − j is a multiple of 3, the graph has a unique 3-coloring. The diameter of the graph can also be expressed as a function of i and j: d = └(2i + j)/3┘. As a result of its highly symmetric topology, the graph is employed in modeling and analysis of cellular and interconnection networks. A more appropriate way of modeling highly dense cellular networks is shown to be the model using the triangular lattice in which the nodes represent the transceivers of the network, rather than the traditional hexagonal lattice where coverage overlap regions cannot be explicitly represented. The toroidal embedding of the triangular lattice using the T_i,j, graph helps us model and simulate the functionality of a cellular network with strong overlap regions without inducing any artifacts due to boundary effects limitations, simultaneously preserving the regularity of the graph model. For the constructing parameters of T_i,j, such that j = i − 1, the graph is optimal with maximum connectivity and maximum number of vertices for a locally planar graph, given diameter d, which in this case will be equal to j. This feature makes the T_i,j graph desirable for interconnection networks topology, together with the graph vertices’ algorithmic labeling scheme, presented in this paper.