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.     

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

We show that computing the lexicographically first four-coloring for planar graphs is -hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P≠NP. We discuss this application to non-self-reducibility and provide a general related result. We also discuss when raising a problem's NP-hardness lower bound to -hardness can be valuable.     

Heuristics for laying out information graphs

Computing - The concept of an information graph is introduced as a representation for object-oriented databases. The retrieval layout problem is an optimization problem defined over the class of...     

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

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.     

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.     

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.     

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.     

Active exploration for large graphs

Modern information networks, such as social networks, communication networks, and citation networks, are often characterized by very large sizes and dynamically changing structures. Common solutions to graph mining tasks (e.g., node classification) usually employ an unrestricted sampling-then-mining paradigm to reduce a large network to a manageable size, followed by subsequent mining tasks. However, real-world networks may be unaccessible at once and must be crawled progressively. This can be due to the fact that the size of the network is too large, or some privacy/legal concerns. In this paper, we propose an Active Exploration framework for large graphs, where the goal is to simultaneously carry out network sampling and node labeling in order to build a sampled network from which the trained classifier can have the maximum node classification accuracy. To achieve this goal, we consider a network as a Markov chain and compute the stationary distribution of the nodes by deriving supervised random walks. The stationary distribution helps identify specific nodes to be sampled in the next step, and the labeling process labels the most informative node which in turn strengthens the sampling of the network. To improve the scalability of active exploration for large graphs, we also propose a more efficient multi-seed algorithm that simultaneously runs multiple, parallel exploration processes, and makes joint decisions to determine which nodes are to be sampled and labeled next. The simultaneous, mutually enhanced sampling and labeling processes ensure that the final sampled network contains a maximum number of nodes directly related to the underlying mining tasks. Experiments on both synthetic and real-world networks demonstrate that our active exploration algorithms have much better chance to include target nodes in the sampled networks than baseline methods.     

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     

Three-coloring planar graphs without short cycles

In this paper we prove that every planar graph without cycles of length 4, 6, 7 and 9 is 3-colorable.     

A note on n-tuple colourings and circular colourings of planar graphs with large odd girth

The existence of planar graphs with odd girth 2k+1 and high girth that cannot be (2k+1, k)-coloured was left as an open question by Klostermeyer and Zhang. In this note we show that such graphs exist for arbitrarily large k. We also show that these graphs have fractional chromatic number greater than 2+1/k.     

A distance measure for large graphs based on prime graphs

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.