New tools and results in graph structure theory.

摘要

We first prove a "non-embeddable extensions" theorem for polyhedral graph embeddings. Let G be a "weakly 4-connected" planar graph. We describe a set of constructions that produce a finite list of non-planar graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. The theorem is more general and applies in particular to polyhedral embeddings in any surface.; We discuss an approach to proving Jorgensen's conjecture, which states that if G is a 6-connected graph with no K 6 minor, then it is apex, that is, it has a vertex v such that deleting v yields a planar graph. We relax the condition of 6-connectivity, and prove Jorgensen's conjecture for a certain sub-class of these graphs.; We prove that every graph embedded in the Klein bottle with representativity at least 4 has a K6 minor. Also, we prove that every "locally 5-connected" triangulation of the torus, with one exception, has a K6 minor. (Local 5-connectivity is a natural notion of local connectivity for a surface embedding.) The above theorem uses a locally 5-connected version of the well-known splitter theorem for triangulations of any surface.; We conclude with a theoretically optimal algorithm for the following graph connectivity problem. A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional to the number of vertices and edges, when implemented on a RAM (random access machine).