Isomorphism testing for graphs of bounded genus
By Gary L. Miller. 1980
We present an algorithm which determines isomorphism of graphs in v<supscrpt>O(g)</supscrpt>steps where v is the number of vertices and g is the genus of the graphs. In [FMR 79] an algorithm was presented for embedding graph on surfaces of genus g in v<supscrpt>O(g)</supscrpt> steps. Here we show how to extend this algorithm to isomorphism testing for graphs of small genus. This result is noteworthy for at least two reasons. First, this extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces. Second, this gives one of the few known natural decompositions of the isomorphism problem into an infinite hierarchy of problems P<subscrpt>o</subscrpt>,P<subscrpt>1</subscrpt>,... such that isomorphism testing of problems in P<subscrpt>1</subscrpt> is decidable in time v<supscrpt>O(i)</supscrpt>.
Subfields: Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algorithms & Complexity
Citations in the corpus
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “Efficient GI algorithms do exist for several restricted classes of graphs, such as trees [13], planar graphs [20] and graphs with certain bounded parameters, including valence [22], eigenvalue multiplicity [5] and genus [26].”
- Practical graph isomorphism, II (2013, neutral): “These classes include many earlier classes such as graphs of bounded degree (Luks, 1982), bounded genus (Filotti and Mayer, 1980; Miller, 1980) and bounded tree-width (Bod-laender, 1990).”
- The NP-Completeness Column: An Ongoing Guide (1982, unknown): “I leave this as an open problem, however, as the definition of ‘‘k-contractible’’ given in [ 61 ] is too convoluted for me to decipher.”