>Algorithmic_Problems_On_Graph_Minors
Table of Contents:
- Principal Investigator.
- Productivity Measures.
- Summary of Objectives and Approach.
- Detailed Summary of Technical Progress.
- Transitions and DOD Interactions.
- Software and Hardware Prototypes.
- List of Publications.
- Invited and Contributed Presentations.
- Honors, Prizes or Awards Received.
- Project Personnel Promotions.
- Project Staff.
- Multimedia URL.
- Keywords.
- Business Office.
- Expenditures.
- Students.
- Book Plans.
- Sabbatical Plans.
- Related Research.
- History.
Principal Investigator.
- PI Name: Neil_Robertson
- PI Institution: The_Ohio_State_University
- PI Phone Number: 614_292_0602
- PI Fax Number: 614_292_1479
- PI Street Address: 120_Chaucer_Court
- PI City,State,Zip: Worthington_Ohio_43085
- PI E-mail Address: robertso@math.ohio-state.edu
- PI URL Home Page: http://www.math.ohio-state.edu/~robertso
- Grant Title: Algorithmic_problems_on_graph_minors
- Grant/Contract Number: N00014-92-J-1965
- R&T Number: 1115048RFW01
- Period of performance: 01_Oct_92-27_Feb_97
- Today's Date: 16_Nov_95
Productivity Measures.
- Number of refereed papers submitted not yet published: 24
- Number of refereed papers published: 13
- Number of unrefereed reports and articles: 0
- Number of books or parts thereof submitted but not published: 0
- Number of books or parts thereof published: 1
- Number of project presentations: 0
- Number of patents filed but not yet granted: 0
- Number of patents granted and software copyrights: 0
- Number of graduate students supported >= 25% of full time: 1
- Number of post-docs supported >= 25% of full time: 2
- Number of minorities supported: 0
Summary of Objectives and Approach.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Prototype Name: The four color programs
- Type: software
- URL: ftp.math.gatech.edu directory pub/users/thomas/four
- Availability: unlimited distribution
- Description: Has all the programs and data supplementary
to the paper `The four-colour theorem' by N. Robertson, D. P. Sanders, P. D.
Seymour and R. Thomas, arranged in two parts, reducibility and discharging.
List of Publications.
- Oleg Borodin and Daniel Sanders, "On light edges and triangles in planar
graphs of minimum degree five, Mathematische Nachrichten 170 (1994) 19-24.
- Daniel Sanders and Yue Zhao, "On diagonally 10-coloring plane
triangulations", J. Graph Theory 20 (1995) 77-85.
- Daniel Sanders and Yue Zhao, "A note on the three color problem", Graphs
and Combinatorics 11 (1995) 91-94.
- Daniel Sanders, "A new proof of the four color theorem", Newsletter of the
SIAM Activity Group on Discrete Mathematics, 4 (1994) 6-7.
- Neil Robertson and Paul Seymour, "Graph minors. XI. Circuits on a
surface", J. Combinatorial Theory, 60B (1994) 72-106.
- Neil Robertson and Paul Seymour, "Graph minors. XII. Distance on a
surface", J. Combinatorial Theory, 64B (1995) 240-272.
- Neil Robertson and Paul Seymour, "Graph minors. XIII. The disjoint paths
problem", J. Combinatorial Theory, 63B (1995) 65-110.
- Neil Robertson, Paul Seymour and Robin Thomas, "Quickly excluding a planar
graph", J. Combinatorial Theory, 62B (1994) 323-348.
- Neil Robertson, Paul Seymour and Robin Thomas, "Kuratowski chains", J.
Combinatorial Theory, 64B (1995) 127-154.
- Neil Robertson, Paul Seymour and Robin Thomas, "Petersen family minors",
J. Combinatorial Theory, 64B (1995) 155-184.
- Neil Robertson, Paul Seymour and Robin Thomas, "Sach's linkless embedding
conjecture", J. Combinatorial Theory, 64B (1995) 185-227.
- Joseph Fiedler, Philip Huneke, Bruce Richter, and Neil Robertson,
"Computing the orientable genus of projective graphs", J. Graph Theory 20
(1995) 297-308.
- Neil Robertson and Paul Seymour, "Graph minors. XIV. Excluding an
Embedding", J. Combinatorial Theory, 65B (1995) 23-50.
- 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.
- 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.
- AMS meeting at the University of Central Florida, Orlando, Florida: "Binary
matroids of branch-width three", 20 minutes, March 1995.
- The R. C. Bose Memorial conference, Fort Collins, Colorado: "The four-color
theorem", 36 minutes, June 1995.
- The third Slovene international conference in graph theory, Bled, Slovenia:
"Results and problems about representativity of graph embeddings", 50 minutes,
June 1995.
- The AMS, IMS, Siam Joint Summer Research Conference, University of
Washington, Seattle, Washington: "Binary matroids of branch-width three", 45
minutes, July 1995.
- AMS meeting in Guanajuato, Mexico: "Planar graphs on nonplanar surfaces",
20 minutes, November 1995.
Honors, Prizes or Awards Received.
Project Personnel Promotions.
- Daniel Sanders was promoted to a three year position as Assistant Professor
at the Ohio State University beginning October 1, 1995.
Project Staff.
- Name: Dr Neil Robertson
- Homepage
- Position: Professor
- Task: principal investigator
- Name: Dr Daniel Sanders
- Homepage
- Position: Assistant Professor
- Task: research
- Name: Dr Yue Zhao
- Position: Lecturer
- Task: research
Multimedia URL.
- EOYL FY95
- QUAD FY95
- EOYL FY94
Keywords.
- Graph_minors
- Excluded_minors
- Graph_colorings
- Surface_embeddings
- Graph_algorithms
- Tree-width
- Directed_circuits
- Matroid_minors
Business Office
- Business Office Phone Number: 614-292-6643
- Business Office Fax Number: 614-292-4315
- Business Office Email: Williard.7@osu.edu
Expenditures
- Est. FY96: 100%
- FY95: 100%
- FY94: 100%
- FY93: 100%
Students
- 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
- Fellows
History
- 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.