Monday October 22nd at 4.30pm

non-orientable), we give a linear time to test the graph isomorphism

of two graphs G,H, one of which has a 2-cell embedding (or has a

polyhedral embedding) into S, i.e., every face is homeormorphic to

a disc. This improves previously known result whose time complexity

is $n^{O(g)}$. Our result is also a far-reaching generalization of

the seminal result of Hopcroft and Wong which says the graph

isomorphism problems for planar graphs can be tested in linear time.

In order to prove our result, we give a linear time algorithm for

the following problem, which is of independent interest.

For each surface S, an integer $k \geq 3$ and a graph G,

find either - an embedding of G in S with representativity (or face-width) at

least k, or - a minor of G which is not embeddable in S with representativity

(or face-width) at least k and is minimal with this property.

Moreover, if there is an embedding, the algorithm can give all the

embeddings of this property, up to Whitney switch. Here,

representativity (or face-width) is the minimum number of points

that every noncontractible closed curve in the surface intersects

the graph.

This result can be viewed as a generalization of Mohar's graph

embedding algorithm, since it gives all specific embeddings.

Moreover, in the proof of the above algorithm, we also give a

simpler proof and better bound for the theorem by Mohar and

Robertson, which is concerning the number of polyhedral embeddings.

Joint work with Bojan Mohar.