Show simple item record

dc.contributor.authorHegde, Rajneeshen_US
dc.date.accessioned2006-06-09T18:09:37Z
dc.date.available2006-06-09T18:09:37Z
dc.date.issued2006-03-30en_US
dc.identifier.urihttp://hdl.handle.net/1853/10481
dc.description.abstractWe 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).en_US
dc.format.extent1137497 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraph algorithmsen_US
dc.subjectGraph minors
dc.subjectGraph theory
dc.titleNew Tools and Results in Graph Structure Theoryen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Prof. Robin Thomas; Committee Member: Prof. Bill Cook; Committee Member: Prof. Prasad Tetali; Committee Member: Prof. Richard Duke; Committee Member: Prof. Xingxing Yuen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record