Algorithms for multicommodity flows in planar graphs

This paper gives efficient algorithms for the muiticommodity flow problem for two classes C₁₂ and C₀₁ of planar undirected graphs. Every graph in C₁₂ has two face boundaries B₁ and B₂ such that each of the source-sink pairs lies on B₁ or B₂. On the other hand, every graph inC ₀₁ has a face boundaryB ₁ such that some of the source-sink pairs lie onB ₁ and all the other pairs share a common sink lying onB ₁. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.     

Algorithms for routing in planar graphs

Summary A routing problem is given by a planar graph G= (V, E) with a given embedding into the plane and a set Ne of nets. A net is a pair of points on the boundary of the infinite face. The goal is to find a set of pairwise edge-disjoint paths connecting the terminals of the various nets. We assume that the degree of every vertex not on the boundary of the infinite face is even and call such routing problems half-even. We show that one can decide in time O(bn) whether a half-even problem is solvable and that a solution can be constructed in time O(n ²). Here n=¦V¦ and b is the number of vertices on the boundary of the infinite face. If the routing problem is even, i.e. every cut has even free capacity, and G is a subgraph of the planar grid then a solution can be found in time O(n ^3/2).This research was supported by the Deutsche Forschungsgemeinschaft, SFB 124, VLSI-Entwurfsmethoden und Parallelität. Part of it was done while the second author was visiting SIEMENS A.G., ZTI VENUS     

Projected Newton methods and optimization of multicommodity flows

A superlinearly convergent Newton like method for linearly constrained optimization problems is adapted for solution of multicommodity network flow problems of the type arising in communication and transportation networks. We show that the method can be implemented approximately by making use of conjugate gradient iterations without the need to compute explicitly the Hessian matrix. Preliminary computational results suggest that this type of method is capable of yielding highly accurate solutions of nonlinear multicommodity flow problems far more efficiently than any of the methods available at present.     

Algorithms for searching massive graphs

Given a large graph, stored on disk, there is often a need to perform a search over this graph. Such a need could arise, for example, in the search component of a data-intensive expert system or to solve path problems in deductive database systems. In this paper, we present a novel data structuring technique and show how a branch-and-bound search algorithm can use this data structuring to prune the search space. Simulation results confirm that, using these techniques, a search can be expedited significantly without incurring a large storage penalty. As a side benefit, it is possible to organize the search to obtain successive approximations to the desired solution with considerable reduction in the total search     

Algorithms for distributing traffic flows

We discuss models and algorithms of distributing traffic flows in the network of a large city or an algomeration. We provide comparative analysis of different algorithms for finding an equilibrium distribution in a transportation network. We discuss the problem of ambiguity in distributing correspondences by the paths in equilibrium and the use of entropy models to avoid this ambiguity.     

An algorithm for drawing planar graphs

A simple algorithm for drawing 3‐connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical structures Vega. Some examples of derived figures are given. Copyright © 1999 John Wiley & Sons, Ltd.     

Algorithms for constructing minimal deduction graphs

Two algorithms for constructing minimal deduction graphs (MDG) for inferring rules and facts in an extended version of the Horn clause logic are described. A deduction graph (DG) is minimal if the number of arcs in the graph is minimized. Horn clauses (HC) are extended to Horn formulas (HF), such that the head or the body of an HF can be a conjunction of positive literals or a disjunction of the bodies of some rule instances, respectively. Each algorithm constructs an MDG from its source to its sink, whose arcs infer the HF `if source then sink'. The construction of an MDG is based on a sound and complete set of inference rules of reflexivity, transitivity, and conjunction for HFs which proceeds by expanding a tree rooted at its sink until its source has a successful backtracking to the root. Then the MDG is extracted from the tree. The nodes being expanded in such a tree are classified into seven types, which are assigned by different priorities for their growing into subtrees or for their pruning to reduce the tree space     

A self-stabilizing algorithm for coloring planar graphs

Summary This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a selfstabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one. Sukumar Ghosh received his Ph.D. degree in Computer Science from Calcutta University in 1971. From 1969 to 1984, he taught at Jadavpur University, Calcutta. During 1976–77, he was a Fellow of the Alexander von Humboldt Foundation at the University of Dortmund, Germany. Since 1984, he is with the Department of Computer Science of the University of Iowa. His current research interests are in the areas of Distributed Systems, Petri Nets and Self-Stabilizating Systems. Mehmet Hakan Karaata received the Sc. B. degree in Computer Science and Engineering from Hacettepe University in Turkey in 1987, and the M.S. degree in Computer Science from the University of Iowa in 1990. He is currently studying towards his Ph.D. at the same university. His research interests are in the areas of Distributed Systems, Self-Stabilizing Systems and Database Systems.This research was supported in part by the National Science Foundation under grant CCR-9109078, and the Old Gold Summer Fellowship of the University of Iowa. An abstract of this paper was presented at the 29th Allerton Conference on Control, Communication & Computing in October 1991.     

Heuristics for rapidly four-coloring large planar graphs

We present several algorithms for rapidly four-coloring large planar graphs and discuss the results of extensive experimentation with over 140 graphs from two distinct classes of randomly generated instances having up to 128,000 vertices. Although the algorithms can potentially require exponential time, the observed running times of our more sophisticated algorithms are linear in the number of vertices over the range of sizes tested. The use of Kempe chaining and backtracking together with a fast heuristic which usually, but not always, resolves impasses gives us hybrid algorithms that: (1) successfully four-color all our test graphs, and (2) in practice run, on average, only twice as slow as the well-known, nonexact, simple to code, (n) saturation algorithm of Brélaz.The work of H. D. Shapiro was performed in part while he was on sabbatical at the Graz University of Technology.     

Heuristics for rapidly four-coloring large planar graphs

We present several algorithms for rapidly four-coloring large planar graphs and discuss the results of extensive experimentation with over 140 graphs from two distinct classes of randomly generated instances having up to 128,000 vertices. Although the algorithms can potentially require exponential time, the observed running times of our more sophisticated algorithms are linear in the number of vertices over the range of sizes tested. The use of Kempe chaining and backtracking together with a fast heuristic which usually, but not always, resolves impasses gives us hybrid algorithms that: (1) successfully four-color all our test graphs, and (2) in practice run, on average, only twice as slow as the well-known, nonexact, simple to code, Θ(n) saturation algorithm of Brélaz.     

On linear-time algorithms for five-coloring planar graphs

Certain properties of planar graphs are established in a particularly straightforward fashion. These properties assure good performance in two linear-time algorithms for five-coloring planar graphs. A new linear-time algorithm, based on a third property, is also presented.     

Generating random connected planar graphs

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators.     

Parallel Approximation Schemes for problems on planar graphs

 This paper describes a technique to obtain NC Approximations Schemes for the Maximum Independent Set in planar graphs and related optimization problems. The strategy consists in decomposing the graph into k-outerplanar subgraphs and solve for each k-outerplanar using tree contraction techniques. Received November 2, 1993/February 14, 1995     

Matching and spanning in certain planar graphs

Call a connected planar graphG legal if it has at least two nodes, no parallel edges or self-loops and at most two terminals (degree 1 nodes) and all terminals and degree 2 nodes are exterior. This class of graphs arose in connection with a two-dimensional generating system for modeling growth by binary cell division. Showing that any permitted pattern can be generated properly requires a matching or pairing lemma. The vertex set of a legal graph withn nodes can be split intop adjacent pairs ands singletons withs p, resulting in a matching which includes at least \(2\left[ {\frac{n}{3}} \right]\) nodes. This bound is sharp in the sense that there are legal graphs for which this matching is maximum. The matching can be implemented by a linear time algorithm. A legal graph witht terminals and n≥4 nodes has a spanning tree with at most \(\left[ {\frac{{n - t}}{2}} \right] + t\) terminals; this bound is sharp. Such a spanning tree can be constructed by an algorithm which operates in almost linear time.     

Connecting face hitting sets in planar graphs

We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.     

Flow in planar graphs with vertex capacities

Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).A preliminary version of this paper appeared in theProceedings of the First Integer Programming and Combinatorial Optimization Conference, Waterloo, Canada, May 1990, pp. 367–383. Samir Khuller is currently supported by NSF Grant CCR-8906949. Part of this research was done while he was visiting the IBM Thomas J. Watson Research Center and was supported by an IBM Graduate Fellowship at Cornell University. Joseph Naor's work was supported by Contract ONR N00014-88-K-0166 while he was a post-doctoral fellow in the Department of Computer Science at Stanford University.