Graph Algorithms and Applications 4

The following sections are included:

• Preface

• Journal of Graph Algorithms and Applications

• Contents

We carry out a detailed empirical analysis of simple heuristics and provable algorithms for bilateral contract-satisfaction problems. Such problems arise due to the proposed deregulation of the electric utility industry in the USA. Given a network and a (multi)set of pairs of vertices (contracts) with associated demands, the goal is to find the maximum number of simultaneously satisfiable contracts. Four different algorithms (three heuristics and a provable approximation algorithm) are considered and their performance is studied empirically in fairly realistic settings using rigorous statistical analysis. For this purpose, we use an approximate electrical transmission network in the state of Colorado. Our experiments are based on the statistical technique Analysis of Variance (ANOVA), and show that the three heuristics outperform a theoretically better algorithm. We also test the algorithms on four types of scenarios that are likely to occur in a deregulated marketplace. Our results show that the networks that are adequate in a regulated marketplace might be inadequate for satisfying all the bilateral contracts in a deregulated industry.

This paper presents the first non-trivial lower bounds for the total number of bends in 3-D orthogonal graph drawings with vertices represented by points. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs, multigraphs, and pseudographs (2 ≤ c ≤ 6) of maximum degree Δ (3 ≤ Δ ≤ 6), with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the ‘2-bends problem’, which is one of the most important open problems in the field.

Since Q_n, the hypercube of dimension n, is known to have n link disjoint paths between any two nodes, the links of Q_n can be partitioned into multiple link-disjoint spanning subnetworks, or factors. We seek to identify factors which efficiently simulate Q_n, while using only a portion of the links of Q_n. We seek to identify (n/2)-factorizations, of Q_n where 1) the factors have as small a diameter as possible, and 2) mappings (embeddings) of Q_n to each of the factors exist, such that the maximum number of links in a factor corresponding to one link in Q_n, (dilation), is as small as possible. In this paper we consider two algorithms for generating Hamilton decompositions of Q_n, and three methods for constructing (n/2)-factorizations of Q_n for specific values of n. The most notable (n/2)- factorization of Q_n results in two mutually isomorphic factors, each with diameter n + 2, where an embedding exists which maps Q_n to each of the factors with constant dilation.

The following sections are included:

• Introduction

• Scanning the Issue

Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open. For example, no space- and I/O-efficient algorithms are known for depth-first search or breath-first search in sparse graphs. In this paper, we present two new results on I/O-efficient depth-first search in an important class of sparse graphs, namely undirected embedded planar graphs. We develop a new depth-first search algorithm that uses O(sort(N) log(N/M)) I/Os, and show how planar depth-first search can be reduced to planar breadthfirst search in O(sort(N)) I/Os. As part of the first result, we develop the first I/O-efficient algorithm for finding a simple cycle separator of an embedded biconnected planar graph. This algorithm uses O(sort(N)) I/Os.

We show that, for any n-vertex graph G and integer parameter k, there are at most 3^4k−n4^n−3k maximal independent sets I ⊂ G with |I| ≤ k, and that all such sets can be listed in time . These bounds are tight when n/4 ≤ k ≤ n / 3. As a consequence, we show how to compute the exact chromatic number of a graph in time , improving a previous algorithm of Lawler (1976).

We show that there exists a linear time algorithm for deciding whether a graph of bounded tree-width has clique-width k for some fixed integer k.

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 search engines to cope with the explosive growth and diversification of the Web. Closely related methods have been used in other disciplines for quite some time.

We propose a visualization method that supports the simultaneous exploration of a link structure and a ranking of its nodes by showing the result of the ranking algorithm in one dimension and using graph drawing techniques in the remaining one or two dimensions to show the underlying structure. We suggest to use a simple spectral layout algorithm, because it does not add to the complexity of an implementation already used for ranking, but nevertheless produces meaningful layouts. The effectiveness of our visualizations is demonstrated with example applications, in which they provide valuable insight into the link structure and the ranking mechanism alike. We consider them useful for the analysis of query results, maintenance of search engines, and evaluation of Web graph models.

In this paper, we consider the problem of finding a mixed upward planarization of a mixed graph, i.e., a graph with directed and undirected edges. The problem is a generalization of the planarization problem for undirected graphs and is motivated by several applications in graph drawing. We present a heuristic approach for this problem which provides good quality and reasonable running time in practice, even for large graphs. This planarization method combined with a graph drawing algorithm for upward planar graphs can be seen as a real alternative to the well known Sugiyama algorithm.

An upward embedding of an embedded planar graph specifies, for each vertex v, which edges are incident on v “above” or “below” and, in turn, induces an upward orientation of the edges from bottom to top. In this paper we characterize the set of all upward embeddings and orientations of an embedded planar graph by using a simple flow model, which is related to that described by Bousset [3] to characterize bipolar orientations. We take advantage of such a flow model to compute upward orientations with the minimum number of sources and sinks of 1-connected embedded planar graphs. We finally devise a new algorithm for computing visibility representations of 1-connected planar graphs using our theoretic results.

The crossing number of a graph G = (V,E), denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Wee assume that the drawing is good, i.e., incident edges do not cross, two edges cross at most once and at most two edges cross in a point of the plane. Leighton [13] proved that for any n-vertex graph G of bounded degree, its crossing number satisfies cr(G)+n = ω(bw²(G)), where bw(G) is the bisection width of G. The lower bound method was extended for graphs of arbitrary vertex degrees to in [16, 20], where d_v is the degree of any vertex v. We improve this bound by showing that the bisection width can be replaced by a larger parameter - the cutwidth of the graph. Our result also yields an upper bound for the path-width of G in terms of its crossing number.

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G₀, G₁, …, G_L. The coarsest graph, G_L, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for G_l is taken from its coarser and smaller child graph, G_l+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

We present a heuristic search algorithm for the ℝ^d Manhattan shortest path problem that achieves front-to-front bidirectionality in subquadratic time. In the study of bidirectional search algorithms, front-to-front heuristic computations were thought to be prohibitively expensive (at least quadratic time complexity); our algorithm runs in O(nlog^dn) time and O(nlog^d−1n) space, where n is the number of visited vertices. We achieve this result by embedding the problem in ℝ^d+1 and identifying heuristic calculations as instances of a dynamic closest-point problem, to which we then apply methods from computational geometry.

This Special Issue brings together selected papers from the Ninth Annual Symposium on Graph Drawing, held in Vienna, Austria, on September 23–26, 2001. We have invited the strongest papers in the ranking generated by the GD program committee and we are glad that the following five papers could be included into this special issue after a strong refereeing process…

We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms for constructing it. The main advantage of the polar representation is that it allows independent control over grid size and bend positions. We first describe a standard (Cartesian) representation algorithm, CRA, which we then modify to obtain a polar representation algorithm, PRA. In both algorithms we are concerned with the following drawing criteria: angular resolution, bends per edge, vertex resolution, bend-point resolution, edge separation, and drawing area.

The CRA algorithm achieves 1 bend per edge, unit vertex and bend resolution, edge separation, drawing area and angular resolution, where d(v) is the degree of vertex v. The PRA algorithm has an improved angular resolution of , 1 bend per edge, and unit vertex resolution. For the PRA algorithm, the bend-point resolution and edge separation are parameters that can be modified to achieve different types of drawings and drawing areas. In particular, for the same parameters as the CRA algorithm (unit bend-point resolution and edge separation), the PRA algorithm creates a drawing of size .

In an orthogonal drawing of a plane graph each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A bend is a point at which the drawing of an edge changes its direction. Every plane graph of the maximum degree at most four has an orthogonal drawing, but may need bends. A simple necessary and sufficient condition has not been known for a plane graph to have an orthogonal drawing without bends. In this paper we obtain a necessary and sufficient condition for a plane graph G of the maximum degree three to have an orthogonal drawing without bends. We also give a linear-time algorithm to find such a drawing of G if it exists.

This paper investigates the following question: Given a grid φ, where φ is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at (integral) grid points of φ? We characterize the trees that can be drawn on a strip, i.e., on a two-dimensional n × 2 grid. For arbitrary graphs we prove lower bounds for the height k of an n × k grid required for a drawing of the graph. Motivated by the results on the plane we investigate restrictions of the integer grid in 3D and show that every outerplanar graph with n vertices can be drawn crossing-free with straight lines in linear volume on a grid called a prism. This prism consists of 3n integer grid points and is universal – it supports all outerplanar graphs of n vertices. We also show that there exist planar graphs that cannot be drawn on the prism and that extension to an n × 2 × 2 integer grid, called a box, does not admit the entire class of planar graphs.

We prove that every tree T = (V, E) on n vertices with edges of unit length can be embedded in the plane with distortion ; that is, we construct a mapping f:V → R² such that for every u,v ∈ V, where ρ(u,v) denotes the length of the path from u to v in T. The embedding is described by a simple and easily computable formula. This is asymptotically optimal in the worst case. We also construct interesting optimal embeddings for a special class of trees (fans consisting of paths of the same length glued together at a common vertex).

We give a characterization of DFS cotree-critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE (Public Implementation of a Graph Algorithm Library and Editor [2]) by the authors, and deduce a justification of a very simple algorithm for finding a Kuratowski subdivision in a DFS cotree-critical graph.