**Contemporary Mathematics**

Volume: 147;
1993;
688 pp;
Softcover

MSC: Primary 05;
Secondary 68; 06; 57

Print ISBN: 978-0-8218-5160-9

Product Code: CONM/147

List Price: $103.00

AMS Member Price: $82.40

MAA Member Price: $92.70

**Electronic ISBN: 978-0-8218-7738-8
Product Code: CONM/147.E**

List Price: $103.00

AMS Member Price: $82.40

MAA Member Price: $92.70

# Graph Structure Theory

Share this page *Edited by *
*Neil Robertson; Paul Seymour*

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

## Graph Structure Theory

- Contents v6 free
- Preface ix10 free
- Alphabetical list of authors xi12 free
- Polynomials 116 free
- Tutte invariants for 2-polymatroids 924
- Extremal matroid theory 2136
- Subexponentially computable truncations of Jones-type polynomials 6378
- Knots and braids: Some algorithmic questions 109124
- A survey of linkless embeddings 125140
- On a new graph invariant and a criterion for planarity 137152
- Four problems on plane graphs raised by Branko Grünbaum 149164
- Counterexamples to a conjecture of Las Vergnas and Meyniel 157172
- An extremal function for the achromatic number 161176
- The asymptotic structure of H-free graphs 167182
- Induced minors and related problems 179194
- Induced circuits in graphs on surfaces 183198
- Tree-representation of directed circuits 195210
- Intercyclic digraphs 203218
- Eulerian trails through a set of terminals in specific, unique and all orders 247262
- 2-reducible cycles containing two specified edges in (2k+1 )-edge-connected graphs 259274
- Edge-disjoint cycles in n-edge-connected graphs 279294
- Finding disjoint trees in planar graphs in linear time 295310
- Surface triangulations without short noncontractible cycles 303318
- Representativity and flexibility on the projective plane 341356
- On non-null separating circuits in embedded graphs 349364
- Projective-planar graphs with even duals II 363378
- 2-factors, connectivity, and graph minors 381396
- A conjecture in topological graph theory 387402
- On the closed 2-cell embedding conjecture 391406
- Cycle cover theorems and their applications 405420
- Cones, lattices and Hilbert bases of circuits and perfect matchings 419434
- Regular maps from voltage assignments 441456
- The infinite grid covers the infinite half-grid 455470
- Dominating functions and topological graph minors 461476
- Notes on rays and automorphisms of locally finite graphs 477492
- Quasi-ordinals and proof theory 485500
- Minor classes: Extended abstract 495510
- Well-quasi -ordering finite posets 511526
- The immersion relation on webs 517532
- Structural descriptions of lower ideals of trees 525540
- Finite automata, bounded treewidth, and well-quasiordering 539554
- Graph grammars, monadic second-order logic and the theory of graph minors 565580
- Graph reductions, and techniques for finding minimal forbidden minors 591606
- An upper bound on the size of an obstruction 601616
- An obstruction-based approach to layout optimization 623638
- Decomposing 3-connected graphs 631646
- Graph planarity and related topics 635650
- 1. Introduction 636651
- 2. The main concepts and notation 637652
- 3. Some classical results 639654
- 4. Simple reductions of the graph planarity problem 640655
- 5. Subdivisions of K5 , K3,3, and L in a graph 641656
- 6. Subdivisions of K3,3 in a 3-connected graph with some edges not subdivided 643658
- 7. A vertex in a matroid and the corresponding notion and dual notion for graphs 644659
- 8. More about non-separating circuits in a graph 648663
- 9. Triangle and 3-cut reductions of the graph planarity problem 652667
- 10. Subdivisions of K, M, and N in quasi 4-connected graphs 654669
- 11. An ear-like decomposition for quasi 4-connected graphs 655670
- 12. Non–separating circuits in quasi 4-connected graphs 659674
- 13. Some refinements of Whitney's planarity criterion 661676
- 14. On Dirac's conjecture 663678
- 15. On Barnette's conjecture 664679
- References 665680

- Excluding a graph with one crossing 669684
- Open problems 677692