Discrete Mathematics and Optimization Seminar

---

KEN-ICHI KAWARABAYASHI
National Institute of Informatics
Monday October 22nd at 4.30pm
Burnside 1205



Title. Graph Isomorphism of Embeddable Graphs In Linear Time

Abstract. For every surface S and its Euler genus g (orientable or
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.