This volume contains the proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, held at the University of Washington in Seattle in the summer of 1991. Among the topics covered are: algorithms on tree-structured graphs, well-quasi-ordering, logic, infinite graphs, disjoint path problems, surface embeddings, knot theory, graph polynomials, matroid theory, and combinatorial optimization.

Readership

Research mathematicians.

Table of Contents

• W. T. Tutte -- Polynomials
• J. Oxley and G. Whittle -- Tutte invariants for \(2\)-polymatroids
• J. P. S. Kung -- Extremal matroid theory
• T. M. Przytycka and J. H. Przytycki -- Subexponentially computable truncations of Jones-type polynomials
• D. J. A. Welsh -- Knots and braids: Some algorithmic questions
• N. Robertson, P. D. Seymour, and R. Thomas -- A survey of linkless embeddings
• Y. C. de Verdière -- On a new graph invariant and a criterion for planarity
• O. Borodin -- Four problems on plane graphs raised by Branko Grünbaum
• B. Reed -- Counterexamples to a conjecture of Las Vergnas and Meyniel
• B. Bollobás, B. Reed, and A. Thomason -- An extremal function for the achromatic number
• H. J. Prömel and A. Steger -- The asymptotic structure of \(H\)-free graphs
• M. Fellows, J. Kratochvíl, M. Middendorf, and F. Pfeiffer -- Induced minors and related problems
• A. Schrijver -- Induced circuits in graphs on surfaces
• A. Frank and T. Jordán -- Tree-representation of directed circuits
• W. McCuaig -- Intercyclic digraphs
• J. Bang-Jensen and S. Poljak -- Eulerian trails through a set of terminals in specific, unique, and all orders
• H. Okamura -- \(2\)-reducible cycles containing two specified edges in \((2k+1)\)-edge-connected graphs
• A. Huck -- Edge-disjoint cycles in \(n\)-edge-connected graphs
• B. A. Reed, N. Robertson, A. Schrijver, and P. D. Seymour -- Finding disjoint trees in planar graphs in linear time
• T. M. Przytycka and J. H. Przytycki -- Surface triangulations without short noncontractible cycles
• R. P. Vitray -- Representativity and flexibility on the projective plane
• X. Zha and Y. Zhao -- On non-null separating circuits in embedded graphs
• S. Negami -- Projective-planar graphs with even duals II
• N. Dean and K. Ota -- \(2\)-factors, connectivity, and graph minors
• J. P. Huneke -- A conjecture in topological graph theory
• X. Zha -- On the closed \(2\)-cell embedding conjecture
• C.-Q. Zhang -- Cycle cover theorems and their applications
• L. A. Goddyn -- Cones, lattices, and Hilbert bases of circuits and perfect matchings
• P. Gvozdjak and J. Širáň -- Regular maps from voltage assignments
• B. Oporowski -- The infinite grid covers the infinite half-grid
• R. Diestel -- Dominating functions and topological graph minors
• H. A. Jung -- Notes on rays and automorphisms of locally finite graphs
• L. Gordeev -- Quasi-ordinals and proof theory
• D. Vertigan -- Minor classes: Extended abstract
• J. Gustedt -- Well-quasi-ordering finite posets
• G. Ding -- The immersion relation on webs
• N. Robertson, P. D. Seymour, and R. Thomas -- Structural descriptions of lower ideals of trees
• K. Abrahamson and M. Fellows -- Finite automata, bounded treewidth, and well-quasiordering
• B. Courcelle -- Graph grammars, monadic second-order logic, and the theory of graph minors
• A. Proskurowski -- Graph reductions, and techniques for finding minimal forbidden minors
• J. Lagergren -- An upper bound on the size of an obstruction
• M. A. Langston -- An obstruction-based approach to layout optimization
• C. R. Coullard and D. K. Wagner -- Decomposing \(3\)-connected graphs
• A. K. Kelmans -- Graph planarity and related topics
• N. Robertson and P. Seymour -- Excluding a graph with one crossing
• N. Dean -- Open problems