Matchings of Intersection Graphs and the Maximum Genus Problem

The maximum genus of a connected graph is defined to be the maximum integer $g$ for which the graph has a cellular embedding in an orientable surface of genus $g$.We present the two most popular methods used to determine the maximum genus of a connected graph, contributed by Xuong and Nebesk\'{y}, survey the polynomial-time algorithms available for finding a maximum genus embedding, and discuss the shortcomings of those algorithms. We develop new results on the relationship between maximum genus and maximum matchings on intersection graphs, of spanning trees and cotrees, and introduce a new class of intersection graphs, called {\it facial intersection graphs}, defined for a given plane embedding. We show that for particular planar 2-connected graphs and for embeddings with certain properties, we can calculate the maximum genus using a standard matching algorithm on an optimal facial intersection graph.

Author

• El Sherif, Lara

Language

• en

Keyword

• intersection graphs
• diameter of an embedding
• matchings
• planar embeddings
• maximum genus
• facial intersection graphs

Date created

• 2016

Type of Work

• Dissertation

License

• All rights reserved

Rights statement

• In Copyright

GW Unit

• Mathematics

Degree

• Ph.D.

Advisor

• Abrams, Lowell

Committee Member(s)

• Ullman, Daniel
• Kainen, Paul
• Robinson, E. Arthur
• Przytycki, Józef H.

Persistent URL

•  https://scholarspace.library.gwu.edu/etd/m326m183x