------------------------------------------------------------- Algorithmic Problems On Graph Minors

Algorithmic Problems On Graph Minors

PI: Neil Robertson (CN: N00014-92-J-1965)

Table of Contents

  1. Topics.
  2. Objectives.
  3. Approaches.
  4. Technical Results.

Topics

  1. Graph Structure
  2. Coloring Problems
  3. Matroid Minors
  4. Surface Embeddings

Narrative

  1. Graph minors are obtained by contracting edges in subgraphs. Excluding a minor forces strong structural properties on a graph; it is either not very big or it has many small vertex cutsets, or large parts of it are almost embedded on bounded genus surfaces. Such graphs with connectivity as large as possible will possess these properties with as few degeneracies as possible, and their structure will be easier to understand.

  2. A coloring is itself a structure, but it is not preserved under taking minors. Nevertheless, minor-closed classes of graphs have bounded chromatic number, and exact computation of the bound includes classical coloring problems. For example, the famous 4-color theorem says that all planar graphs are 4-colorable; but planar graphs are determined by two excluded minors. A goal of this project is to settle some open problems related to the 4-color theorem.

  3. Graphs form binary matrices, with rows their vertices, columns their edges and entries 1 if and only if the corresponding row and column are incident. This fact allows for many appropriate graph structure theorems to extend into the binary matrix context and beyond. As the minor relation carries over this is especially true of graph minor structure. It is of interest in this project to carry over some graph minor structure and algorithmic properties.

  4. Surface embeddings form the smooth structural classes for graph minors after low order nontrivial vertex cutsets are removed. The planar case is fairly well understood, and has some features that make it easier to work in, including several efficient linear time algorithms. A good notion of local planarity arises in graph minors and a project goal is to exploit this to put general surfaces on a more solid footing by extending basic planar theorems to them and using local planarity to study existence and flexibility of embeddings.

Objectives

Summary

  1. To develop excluded minor structure of graphs and graph connectivity.
  2. To solve some graph coloring problems related to the 4-color theorem.
  3. To develop algorithms for binary matrices of bounded branch-width.
  4. To study graph surface embedding problems related to local planarity.

Discussion

  1. The minors of a graph are formed by taking subgraphs and then contracting some of their edges to vertices. Graphs with certain minors excluded tend to possess interesting properties relative to graph connectivity and to possible surface embeddings. Assuming an appropriate level of connectivity removes degeneracies in this structure, and provides path linking properties which can be used to help produce the structure excluding the minors.

  2. The 4-color theorem for planar graphs was proved in 1976 by Haken and Appel. Their proof used computer calculations extensively, and was presented in a manner difficult to check. The main possible generalizations were conjectured by Hadwiger and Tutte, and involve general vertex colorings and generalized face colorings. These problems combine excluded minor structure and coloring reductions, and there is hope of using this to make new progress on them.

  3. Graph theorems involving minor inclusion may extend to matroid theory, in particular to binary matroids, the dependency structures on the columns of binary matrices. For graphs, each column has at most two entries 1 and the rows are the vertices. Branch-width k graphs can be reduced to subgraphs of size at most k by repeatedly splitting at noncrossed k-vertex cutsets. Width 3 binary matroids are a natural family to study by analogy with the graph case.

  4. Graph embeddings on a closed surface, not the sphere, can be studied by how essential curves in the surface meet the embedded graph. The fewest number of points in which such curves meet the graph measures the degree of local planarity. Many properties of planar graphs go over to higher surfaces if the degree of local planarity is high enough. The objective here is to study polynomial time algorithmic problems on surface embeddings in this context.

Approaches

Summary

  1. To generalize the known results on 3-connection and 4-connection.
  2. To apply structure theory, coloring reductions, and discharging methods to coloring problems.
  3. To work from graph methods, compositions and the regular matroid case.
  4. To apply surgery techniques, methods of the planar case, planar patches.

Discussion

  1. The study of 3-, 4- and 5-connection can be approached by chains of minors at that level of connectivity. The goal is to refine such chains allowing as little change in the members as possible. At the 6-connected level (also 4-connected without triangles) consecutive graphs in a chain may differ by the square root of the number of vertices. But at the lower connectivities the difference can be kept to a very small constant. This allows constructions of minors that force certain structures, such as apex graph structure (planar plus one vertex). One repairs lower connectivity in the minors by using the path properties of the containing graphs. When minors are being excluded the computer is very helpful as it can be programmed to run over all possible extensions of a given minor, and to test for the excluded minors.

  2. There are standard reduction techniques for extending colorings from certain minors to the containing graph. Concerning the 4-color theorem, it is natural to reduce the problem to internally-6-connected 5-connected triangulations. Reducibility of a configuration bounded by a circuit, say, can be defined in a way that is testable by computer (The Heesch algorithm). The Euler characteristic formula implies that if a charge 6-k is assigned to each valency k vertex, the total charge is 12. The discharging method distributes the positive charge to neighbors so as to leave as little positive charge remaining as possible. Total charge remains 12 and so positively charged vertices must still exist. A contradiction follows by showing they always have reducible configurations in their neighborhoods. As 4-colorings of triangulations are equivalent to edge-3-colorings of their trivalent duals, edge-coloring methods apply and lead to further open questions.

  3. The graph methods carry over to binary matrices. The rows function roughly as vertices when the columns are being treated like edges. Still, theorems like generalizing the characterization of graphs without 5-clique minors, which goes back to 1935, seem almost unapproachable here. This is why the binary obstacles to having width at most 3 are not yet established, though a computer search has produced all the likely candidates. The construction of all width 3 matroids is more approachable and the necessary summing operations are known. Actually, only a localization lemma is needed, and computer work has been helpful here by producing the likely finite set of generating matroids.

  4. The surgery technique is to find families of pairwise noncrossing circuits on a surface such that when the surface is split along the circuits some property is eliminated, such as being nonorientable. Then the graph is recombined to form a new embedding which maintains the lack of the given property, in this case giving an oriented embedding. Another technique is the use of patches to describe two alternative embeddings. These are formed by taking the angles between consecutive edges in the embeddings that agree and replacing them by large planar pieces. These are extended across common edges and faces forming enlargments of the common parts of the embeddings. The two embeddings may then be viewed as the result of reembedding these patches.

Technical_Results

Summary

  1. A structure theory of trivalent cyclically-5-connected graphs without Petersen minors.
  2. A new proof of the 4-color theorem, with quadratic time algorithm, and use of the discharging method to prove several open conjectures.
  3. A thesis involving graphical branch-width, generalization to the binary matrix case, and some compositions which construct the class of branch-width 3 binary matrices.
  4. Results on planar graphs on nonplanar surfaces, on disjoint essential circuits, and on embedding uniqueness on the torus and Klein bottle.

Discussion

  1. Excluding the Petersen graph as a minor is an open problem of great difficulty and with many possible consequences. With Seymour and Thomas we have solved the case for trivalent graphs. Under internal 6-connection and cyclic-5-connection, the graphs nearly embed on the plane. Either the embedding fails by one extra vertex or by two crossings on the infinite region. The problem of separating a pair and triple of vertices by disjoint connected subgraphs is solved in these cases.

  2. The 4-color theorem is proved in a way that is short and free of ambiguities. The unavoidable set of reducible configurations is about half the old size and the discharging rules about a tenth of the old number. Degeneracies in the reducibility test are eliminated, or accounted for. Immersion degeneracies are eliminated and a quadratic algorithm for 4-coloring planar graphs given. Several open problems have been solved using nontrivial applications of the discharging method.

  3. The thesis gives the structure of branch-width 3 graphs. They are constructable from a small finite set by a 3-sum operation and the usual summations of lower order. The obstacle set, of minor-minimal branch-width 4 graphs, has 4 members, on 10 or 12 edges. This is carried over to binary matroids using three general 3-sum operations and 2 special ones. Two conjectures, similar to the graph analogue theorems, imply all binary width 3 matroids are generated.

  4. If a planar graph is embedded on a genus g surface, then g handles exist on the surface, and g pairwise noncrossing circuits, each meeting the graph in at most 2 points, and on its own handle. If a graph G embeds on a surface and G has no disjoint essential circuits, then the embedding is analogous to one of the families of abstract graphs which have no disjoint circuits. Graphs embedded on the torus or Klein bottle with local planarity at least 4 have only 1 such embedding, with one exceptional family on the torus deriving from the 4-cube.