On The Properties Of Minimal Non-planar Graphs And Routing Problems In Edge-transitive Graphs

Minimal non-planar graphs, which are also called Kuratowski subgraphs, arenon-planar graphs with their subgraphs are planar. Obviously,minimal non-planargraph is one kind of critical graphs, because it meets all the properties of non-planargraphs, while any of their proper graphs satisfies the properties of planar graphs.Studying the properties of minimal non-planar graphs plays an important role insurveying non-planar graphs and planar graphs. Edge-transitive graphs are surveyedby the knowledge of group theories. Such graphs can be described that for arbitrarytwo edgese₁,e₂of them, there exists an isomorphic mapping θ∈Aut （G）such thatθ（e₁）=e₂. Caley graphs are transitive graphs. Since many of them have the propertiesof vertex transitivity and edge transitivity, Caley graphs are applied to the research ofthe net widely.15types of Caley graphs were listed by S.Lakshmivivarahan,Jung-Sing Jwo and S.K.Dhall. Routing problems in Caley graphs are also aninteresting research direction for some researchers.The whole work of this thesis can be summarized as followed:1.3typical indexes of minimal non-planar graphs are introduced,that arecrossing number, Kuratowski subgraphs and critical edges. The connection of graphsand properties of strongly regular graph are simply introduced. Also the pre-existingresearch results for Caley graphs are showed.2. By Euler formula, relations among the numbers of edges, vertices and thegirth of minimal non-planar graphs are discussed.3. By Brooks theorem and the theory about proper coloring graphs, the coloringproperties of non-planar graphs are proven.4. It is necessary that Kuratowski subgraphs are contained in non-planargraphs.But for any given edge,it is not always contained in their Kuratowskisubgraphs. The method examined by Frank Harary is applied to the construction of aspecial kind of non-planar graph, any edge of which is contained in one of itsKuratowski subgraph.5. By using the definitions of minimal non-planar graphs and bridge, twotheorems are proven,that are,（1）An edge-transitive graph is a minimal non-planar graph if its crossing numberequals1. （2）When the regular graph satisfies r≥v/2（v≥6）,it is non-planar.6. By Menger Theorem and the generalization ofWhitney Theorem,the numbersof disjoint paths in edge-transitive graphs are discussed,and then the distance of theshortest path and an algorithm concerning how to get to I from an arbitraryvertice p inMB_n are given.