Graph Structure Theory.
Robertson, Neil.
Graph Structure Theory. - 1st ed. - 1 online resource (706 pages) - Contemporary Mathematics ; v.147 . - Contemporary Mathematics .
Intro -- Contents -- Preface -- Alphabetical list of authors -- Polynomials -- Tutte invariants for 2-polymatroids -- Extremal matroid theory -- Subexponentially computable truncations of Jones-type polynomials -- Knots and braids: Some algorithmic questions -- A survey of linkless embeddings -- On a new graph invariant and a criterion for planarity -- Four problems on plane graphs raised by Branko Grünbaum -- Counterexamples to a conjecture of Las Vergnas and Meyniel -- An extremal function for the achromatic number -- The asymptotic structure of H-free graphs -- Induced minors and related problems -- Induced circuits in graphs on surfaces -- Tree-representation of directed circuits -- Intercyclic digraphs -- Eulerian trails through a set of terminals in specific, unique and all orders -- 2-reducible cycles containing two specified edges in (2k+1 )-edge-connected graphs -- Edge-disjoint cycles in n-edge-connected graphs -- Finding disjoint trees in planar graphs in linear time -- Surface triangulations without short noncontractible cycles -- Representativity and flexibility on the projective plane -- On non-null separating circuits in embedded graphs -- Projective-planar graphs with even duals II -- 2-factors, connectivity, and graph minors -- A conjecture in topological graph theory -- On the closed 2-cell embedding conjecture -- Cycle cover theorems and their applications -- Cones, lattices and Hilbert bases of circuits and perfect matchings -- Regular maps from voltage assignments -- The infinite grid covers the infinite half-grid -- Dominating functions and topological graph minors -- Notes on rays and automorphisms of locally finite graphs -- Quasi-ordinals and proof theory -- Minor classes: Extended abstract -- Well-quasi -ordering finite posets -- The immersion relation on webs -- Structural descriptions of lower ideals of trees. Finite automata, bounded treewidth, and well-quasiordering -- Graph grammars, monadic second-order logic and the theory of graph minors -- Graph reductions, and techniques for finding minimal forbidden minors -- An upper bound on the size of an obstruction -- An obstruction-based approach to layout optimization -- Decomposing 3-connected graphs -- Graph planarity and related topics -- 1. Introduction -- 2. The main concepts and notation -- 3. Some classical results -- 4. Simple reductions of the graph planarity problem -- 5. Subdivisions of K5 , K3,3, and L in a graph -- 6. Subdivisions of K3,3 in a 3-connected graph with some edges not subdivided -- 7. A vertex in a matroid and the corresponding notion and dual notion for graphs -- 8. More about non-separating circuits in a graph -- 9. Triangle and 3-cut reductions of the graph planarity problem -- 10. Subdivisions of K, M, and N in quasi 4-connected graphs -- 11. An ear-like decomposition for quasi 4-connected graphs -- 12. Non-separating circuits in quasi 4-connected graphs -- 13. Some refinements of Whitney's planarity criterion -- 14. On Dirac's conjecture -- 15. On Barnette's conjecture -- References -- Excluding a graph with one crossing -- Open problems.
9780821877388
Graph theory -- Congresses.
Electronic books.
QA166 -- .A48 1991eb
511/.5
Graph Structure Theory. - 1st ed. - 1 online resource (706 pages) - Contemporary Mathematics ; v.147 . - Contemporary Mathematics .
Intro -- Contents -- Preface -- Alphabetical list of authors -- Polynomials -- Tutte invariants for 2-polymatroids -- Extremal matroid theory -- Subexponentially computable truncations of Jones-type polynomials -- Knots and braids: Some algorithmic questions -- A survey of linkless embeddings -- On a new graph invariant and a criterion for planarity -- Four problems on plane graphs raised by Branko Grünbaum -- Counterexamples to a conjecture of Las Vergnas and Meyniel -- An extremal function for the achromatic number -- The asymptotic structure of H-free graphs -- Induced minors and related problems -- Induced circuits in graphs on surfaces -- Tree-representation of directed circuits -- Intercyclic digraphs -- Eulerian trails through a set of terminals in specific, unique and all orders -- 2-reducible cycles containing two specified edges in (2k+1 )-edge-connected graphs -- Edge-disjoint cycles in n-edge-connected graphs -- Finding disjoint trees in planar graphs in linear time -- Surface triangulations without short noncontractible cycles -- Representativity and flexibility on the projective plane -- On non-null separating circuits in embedded graphs -- Projective-planar graphs with even duals II -- 2-factors, connectivity, and graph minors -- A conjecture in topological graph theory -- On the closed 2-cell embedding conjecture -- Cycle cover theorems and their applications -- Cones, lattices and Hilbert bases of circuits and perfect matchings -- Regular maps from voltage assignments -- The infinite grid covers the infinite half-grid -- Dominating functions and topological graph minors -- Notes on rays and automorphisms of locally finite graphs -- Quasi-ordinals and proof theory -- Minor classes: Extended abstract -- Well-quasi -ordering finite posets -- The immersion relation on webs -- Structural descriptions of lower ideals of trees. Finite automata, bounded treewidth, and well-quasiordering -- Graph grammars, monadic second-order logic and the theory of graph minors -- Graph reductions, and techniques for finding minimal forbidden minors -- An upper bound on the size of an obstruction -- An obstruction-based approach to layout optimization -- Decomposing 3-connected graphs -- Graph planarity and related topics -- 1. Introduction -- 2. The main concepts and notation -- 3. Some classical results -- 4. Simple reductions of the graph planarity problem -- 5. Subdivisions of K5 , K3,3, and L in a graph -- 6. Subdivisions of K3,3 in a 3-connected graph with some edges not subdivided -- 7. A vertex in a matroid and the corresponding notion and dual notion for graphs -- 8. More about non-separating circuits in a graph -- 9. Triangle and 3-cut reductions of the graph planarity problem -- 10. Subdivisions of K, M, and N in quasi 4-connected graphs -- 11. An ear-like decomposition for quasi 4-connected graphs -- 12. Non-separating circuits in quasi 4-connected graphs -- 13. Some refinements of Whitney's planarity criterion -- 14. On Dirac's conjecture -- 15. On Barnette's conjecture -- References -- Excluding a graph with one crossing -- Open problems.
9780821877388
Graph theory -- Congresses.
Electronic books.
QA166 -- .A48 1991eb
511/.5