Type of Document	Dissertation
Author	Hegde, Rajneesh
URN	etd-03242006-014930
Title	New Tools and Results in Graph Structure Theory
Degree	Doctor of Philosophy
Department	Mathematics
Advisory Committee	Advisor Name Title Prof. Robin Thomas Committee Chair Prof. Bill Cook Committee Member Prof. Prasad Tetali Committee Member Prof. Richard Duke Committee Member Prof. Xingxing Yu Committee Member
Keywords	Graph Algorithms Graph Minors Graph Theory
Date of Defense	2006-02-23
Availability	unrestricted
Abstract 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 K_6 minor. Also, we prove that every ``locally 5-connected' triangulation of the torus, with one exception, has a K_6 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).
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    hegde_rajneesh_d_200605_phd.pdf 1.14 Mb 00:05:15 00:02:42 00:02:22 00:01:11 00:00:06