Graph imbeddings: Theory, complexity and algorithms

Imbedding of a graph is a drawing of the graph that contains no edge crossings. A graph has imbeddings into surfaces of genus between its minimum genus and its maximum genus. Imbedding a graph into surfaces of higher genus is a fundamental and yet difficult problem. It is believed that the answer to a famous open problem in computer science, namely the graph isomorphism problem, perhaps lies in the study of graph imbeddings into higher genus surfaces. Until recently, not much was known about the structure of graphs when imbedded into higher genus surfaces. We present results on combinatorial and computational aspects of graph imbeddings.; We develop a powerful technique called "edge swapping" and use it to prove that the maximum genus is larger than one-quarter of its cycle rank for simplicial graphs. We prove that our lower bound is tight by presenting an infinite class of graphs whose maximum genus can be made arbitrarily close to one-quarter of its cycle rank. This result directly leads to improvements of a number of previous results in the theory of graph imbeddings.; We introduce a new ear decomposition, called the maximum-paired ear decomposition and prove that computing a maximum-paired ear decomposition of a graph of e edges is {dollar}O(esp2){dollar}-time equivalent to computing the maximum genus of the graph. This gives a first polynomial time algorithm for obtaining a maximum-paired ear decomposition.; The equivalence of maximum-paired ear decomposition and maximum genus imbedding enables us to derive a tight lower bound for 2-connected simplicial graphs. We prove that the maximum genus is at least one-third of its cycle rank for all 2-connected simplicial graphs. This lower bound is tight for 2-connected simplicial graphs.; It is known that computing minimum genus imbedding is NP-hard whereas maximum genus imbedding can be computed in polynomial time. We present results on the complexity of computing graph imbeddings of genus between the minimum genus and the maximum genus. We show that computing imbeddings of genus which are "close" to the minimum genus is still NP-hard. On the other hand, we present a linear time approximation algorithm that approximates the minimum genus of a graph of n vertices to either within a constant ratio, or to within a difference of O(n). A polynomial time algorithm for imbedding a graph G into a surface of genus one less than the maximum genus is also presented. This is the first polynomial time algorithm that is known for this problem.