Topological Operations for Genus Distributions and Embeddings of Graphs

Show simple item record

dc.contributor.advisor Sneddon, J en
dc.contributor.advisor Conder, M en Zhu, Zilong en 2013-07-22T01:50:46Z en 2012 en
dc.identifier.uri en
dc.description.abstract The research of graph embeddings on surfaces started from Euler's equation v e+f = 2. For a connected graph G, v, e and f represent the number of vertices, edges and regions of an embedding on a plane or sphere. Genus embedding of graphs is one of the most studied subjects in topological graph theory. A polynomial is used to represent a graph's embedding distribution on di erent surfaces which are classi ed by genus. We discuss orientable genus embeddings of connected undirected graphs which are derived from some other graphs by topological operations, including face-contraction, vertexsplitting, vertex-augment, pearl-making, bouquet-making and face-expansion which are designed to treat one graph. We then consider the Cartesian product, dot product and extended dot product which are designed to be applied between two graphs. Face-contraction, vertex-splitting, vertex-augment, pearl-making, bouquet-making and face-expansion are discussed to achieve partial genus distribution of some graphs, including fan graph Fn, cube-connected cycles CCCn and star-connected cycles SCCn. For several in nite families of graphs, we calculate their minimum and maximum genus and demonstrate constructions of embeddings of all genera between these ranges. The graphs discussed in the thesis are derived from Cartesian product, dot product and a newly de ned extended dot product. en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.rights.uri en
dc.title Topological Operations for Genus Distributions and Embeddings of Graphs en
dc.type Thesis en The University of Auckland en Doctoral en PhD en
dc.rights.holder Copyright: The Author en
pubs.elements-id 404632 en
pubs.record-created-at-source-date 2013-07-22 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace