>Algorithmic_Problems_On_Graph_Minors

Table of Contents:

  1. Principal Investigator.
  2. Productivity Measures.
  3. Summary of Objectives and Approach.
  4. Detailed Summary of Technical Progress.
  5. Transitions and DOD Interactions.
  6. Software and Hardware Prototypes.
  7. List of Publications.
  8. Invited and Contributed Presentations.
  9. Honors, Prizes or Awards Received.
  10. Project Personnel Promotions.
  11. Project Staff.
  12. Multimedia URL.
  13. Keywords.
  14. Business Office.
  15. Expenditures.
  16. Students.
  17. Book Plans.
  18. Sabbatical Plans.
  19. Related Research.
  20. History.

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

  1. A minor M of a graph G is formed by taking a subgraph H and contracting the connected components of a subgraph K of H to vertices. This is a stronger containment relation than taking subgraphs and has a topological flavor. This feature shows up in problems of path linkages and those of surface embeddings. The main objective of this project is to develop structure theory for minor closed classes of graphs, and to develop algorithms operating within these classes.
  2. This usually involves reducing problems, such as finding path linkages, certain minors or rooted minors, graph colorings, surface embeddings or bounded tree-width decompositions, to graphs of an appropriate level of connectivity. Some times the contained objects, like the path linkages in graphs with fixed terminal pairs of vertices, and other times the containing objects, like the surface embeddings or tree-width decompositions, have the primary importance. The interplay between the two kinds of structure is fascinating. For example, if a graph is embedded on a disk with two terminal pairs crossed on the boundary then a disjoint linkage of the terminal pairs is impossible, but if the graph is 4-connected and no such embedding exists then a disjoint linkage always exists.
  3. Graph connectivity divides into three basic parts: how paths link up inside the graph, how chains of minors of a fixed connectivity behave, and how the graph breaks up by tree-structure decompositions. A general detailed framework of connectivity theory is understood up to 3-connection, and analogous results have been obtained for 4-connected graphs. But there are several possible ways to extend the known theorems and also many variations of the definition of connectivity which are natural for solving problems at the level of 4- and 5-connectivity. General results are also known, often related to Menger's path theorem of 1927. An earlier graph minor result of Robertson and Seymour found a low order polynomial-time algorithm for disjoint linkages when a fixed k terminal pairs are specified. However, the focus here is on finding strong structural results concerning graphs of connectivity 4 or 5.
  4. A conjecture since 1852 in graph theory was solved by W. Haken and K. Appel in 1976, that maps on the plane with connected countries can be colored in 4 colors so that countries with a common boundary line receive different colors. There are two main conjectures generalizing this result; Hadwiger's (1943) that loopless graphs without (k+1)-clique minors can always be colored in k colors (when k = 4, this is a consequence of the 4-color theorem) and Tutte's (1957) that graphs without a Petersen graph minor possess nowhere-zero 4-flows. A nowhere-zero flow generalizes proper face-colorings, and so is dual to the usual vertex-colorings of graphs. These theorems and conjectures seem to need considerable computer computations, and the work on them is algorithmical. To understand the proof of the 4-color theoerem and apply it to these problems has been a major focus of our research for the past three years.
  5. Branch-width is a parameter closely related to graph tree-width. Either of these concepts can be imagined as reducing a graph to bounded sized subgraphs by pairwise non-crossing vertex cutsets. Such decompositions allow for linear-time algorithms utilizing the resulting tree-structure of bounded size subgraphs. Branch-width more easily generalizes to matroids, or more concretely, to matrices. The goal here is to study binary matrices from this point of view, generalizing graph theorems. A project in this area is to generalize a theorem about branch-width-3 graphs to binary matrices. The algorithmic theory of graphs has extensions to this area.
  6. A basic problem of graph embeddings on surfaces is to extend planar graph results to the higher surfaces. A measure of the local planarity in graph embeddings on nonplanar surfaces is the smallest number of points in which a nontrivial circuit in the surface meets the embedded graph. This parameter arose in a graph minor theorem to the effect that sufficiently high local planarity implies that any fixed planar embedding can be obtained as a minor. Some problems here concern refinements of this basic theorem for particular included embeddings such as a separating circuit or a clique minor, how "flexible" an embedding of a particular graph can be, which graphs admit embeddings of local planarity at least k, and showing sufficiently highly locally planar embeddings have coloring and Hamiltonian circuit properties similar to planar graphs.

Detailed Summary of Technical Progress.

  1. Excluding the Petersen graph as a minor is a difficult open problem with many possible consequences. 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 linking problem of separating a pair and triple of vertices by disjoint connected subgraphs is also solved in this situation. This work, done earlier, involves computer analysis, is being written in 5 papers.
  2. The new proof of the 4-color theorem has been prepared and submitted for publication. A synopsis can be viewed at Thomas The proof is short and free of ambiguities. Compared to the Appel, Koch and Haken proof, the unavoidable set has 633 members rather than 1528, the discharging method for finding unavoidable sets was programmed with 32 rules instead of working by hand with over 300 rules, and the text and diagrams cover 42 pages rather than 741. Possible immersion degeneracies are eliminated which permits a quadratic-time algorithm for 4-coloring planar graphs rather than their quartic one. The programs are available by anonymous ftp from ftp.math.gatech.edu in the directory pub/users/thomas/four.
  3. Dan Sanders is a coauthor on the 4-color paper. He has also solved with various coauthors, including Yue Zhao, many open problems in the coloring theory of graphs on surfaces by variations of the discharging method, developed over the years regarding the 4-color theorem proof. These papers are available by anonymous ftp from ftp.math.ohio-state in the directory edu/pub/users/robertso.
  4. Two papers with Bojan Mohar on the structure of planar graphs on nonplanar surfaces, and on disjoint essential circuits in graphs on a fixed surface were completed. If a planar graph is embedded on a genus g surface, then we show that 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 has a structure analogous to an abstract graph which has no disjoint circuits.
  5. The most recent successful work was to prove a conjecture of Dan Younger about directed graphs D. We have shown that, for any positive integer k, there is an integer t = t(k) so that either there are at least k disjoint directed circuits in D or at most t vertices are needed to meet all directed circuits in D. This is a well-known problem in combinatorial optimization. The solution uses techniques of Ramsey theory and methods of untangling two intersecting families of directed linkages similar to those developed in graph minors.
  6. John Maharry has found a structure theorem for excluding the cube as a minor. He expects to complete his thesis by Spring quarter of 1996. This involves an infinite family at the 4-connected level, a moderately large number of small exceptions to the family, and a careful analysis to get down to the internally-4-connected case whence the general case follows by standard methods.

Transitions and DOD Interactions.

Software and Hardware Prototypes.

  1. Prototype Name: The four color programs

List of Publications.

  1. Oleg Borodin and Daniel Sanders, "On light edges and triangles in planar graphs of minimum degree five, Mathematische Nachrichten 170 (1994) 19-24.
  2. Daniel Sanders and Yue Zhao, "On diagonally 10-coloring plane triangulations", J. Graph Theory 20 (1995) 77-85.
  3. Daniel Sanders and Yue Zhao, "A note on the three color problem", Graphs and Combinatorics 11 (1995) 91-94.
  4. Daniel Sanders, "A new proof of the four color theorem", Newsletter of the SIAM Activity Group on Discrete Mathematics, 4 (1994) 6-7.
  5. Neil Robertson and Paul Seymour, "Graph minors. XI. Circuits on a surface", J. Combinatorial Theory, 60B (1994) 72-106.
  6. Neil Robertson and Paul Seymour, "Graph minors. XII. Distance on a surface", J. Combinatorial Theory, 64B (1995) 240-272.
  7. Neil Robertson and Paul Seymour, "Graph minors. XIII. The disjoint paths problem", J. Combinatorial Theory, 63B (1995) 65-110.
  8. Neil Robertson, Paul Seymour and Robin Thomas, "Quickly excluding a planar graph", J. Combinatorial Theory, 62B (1994) 323-348.
  9. Neil Robertson, Paul Seymour and Robin Thomas, "Kuratowski chains", J. Combinatorial Theory, 64B (1995) 127-154.
  10. Neil Robertson, Paul Seymour and Robin Thomas, "Petersen family minors", J. Combinatorial Theory, 64B (1995) 155-184.
  11. Neil Robertson, Paul Seymour and Robin Thomas, "Sach's linkless embedding conjecture", J. Combinatorial Theory, 64B (1995) 185-227.
  12. Joseph Fiedler, Philip Huneke, Bruce Richter, and Neil Robertson, "Computing the orientable genus of projective graphs", J. Graph Theory 20 (1995) 297-308.
  13. Neil Robertson and Paul Seymour, "Graph minors. XIV. Excluding an Embedding", J. Combinatorial Theory, 65B (1995) 23-50.
  14. Neil Robertson, Paul Seymour and Robin Thomas, Excluding Infinite Clique Minors, Memoirs of the American Mathematical Society, Volume 118, Number 566 (1995) 103 pp.

Invited and Contributed Presentations.

  1. One week lecture series at the University of New Hampshire, Durham, New Hampshire: "On the proof of the 4-color theorem", 2 hour lectures, and "On the proof of the graph minor theorem", 2 hour lectures, November, 1994.
  2. AMS meeting at the University of Central Florida, Orlando, Florida: "Binary matroids of branch-width three", 20 minutes, March 1995.
  3. The R. C. Bose Memorial conference, Fort Collins, Colorado: "The four-color theorem", 36 minutes, June 1995.
  4. The third Slovene international conference in graph theory, Bled, Slovenia: "Results and problems about representativity of graph embeddings", 50 minutes, June 1995.
  5. The AMS, IMS, Siam Joint Summer Research Conference, University of Washington, Seattle, Washington: "Binary matroids of branch-width three", 45 minutes, July 1995.
  6. AMS meeting in Guanajuato, Mexico: "Planar graphs on nonplanar surfaces", 20 minutes, November 1995.

Honors, Prizes or Awards Received.

Project Personnel Promotions.

  1. Daniel Sanders was promoted to a three year position as Assistant Professor at the Ohio State University beginning October 1, 1995.

Project Staff.

  1. Name: Dr Neil Robertson
  2. Name: Dr Daniel Sanders
  3. Name: Dr Yue Zhao

Multimedia URL.

  1. EOYL FY95
  2. QUAD FY95
  3. EOYL FY94

Keywords.

  1. Graph_minors
  2. Excluded_minors
  3. Graph_colorings
  4. Surface_embeddings
  5. Graph_algorithms
  6. Tree-width
  7. Directed_circuits
  8. Matroid_minors

Business Office

Expenditures

  1. Est. FY96: 100%
  2. FY95: 100%
  3. FY94: 100%
  4. FY93: 100%

    Students

    1. Name: Mr John Maharry
      • Homepage
      • Position: graduate student
      • Nationality: American
      • Available for Summer at DoD Lab: no
      • Task: graph connectivity, coloring and surface embedding
      • Thesis: the structure theory of excluding a cube minor

    Book Plans

    Sabbatical Plans

    Related Research

    1. Fellows

    History

    1. P. D. Seymour and Bill Cook have implemented a path linkage algorithm, called the ring router algorithm, for graphs of branch-width at most 6 as part of a larger systems package, the SONET Toolkit, at Bellcore, Morristown, New Jersey.