Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer-Myrvold planarity algorithm, which has a MATLAB and [C++](http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/boyer_myrvold.html) implementation, and I would like to know if there is something similar for toroidal graphs.



Toroidality testing
Currently there is no *standard* algorithm for testing if a graph can be embedded in a torus. It looks like this is because (1) there isn't too widespread of a need for one yet, and (2) among the available algorithms, there is a huge trade-off between algorithmic complexity and ease-of-implementation so there is no obvious choice.


It looks like one of the more popular algorithms is by Jiahua Yu in *[A Practical Torus Embedding Algorithm and Its Implementation](http://www.ijnc.org/index.php/ijnc/article/view/122)* (2011). Although the algorithms is exponential, it is sufficiently fast for small graphs and doesn't appear to be too difficult to implement.


Prior to Yu, like Gerry Myerson said in the comments, in *[Practical toroidality testing](http://dl.acm.org/citation.cfm?id=314392)* (1997) Neufeld and Myrvold describe an exponential algorithm for checking the toroidality of a graph. Two of Myrvold's students, J. Chambers in *Hunting for torus obstructions* (2002), and J. Woodcock in *[A Faster Algorithm for Torus Embedding](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7808)* (2004), describe implementations of this algorithm.


At the other end of the spectrum, in [this paper](http://dl.acm.org/citation.cfm?id=659462) (1995) Juvan, Marincek, and Mohar *outline* an approach to a linear time toroidality testing algorithm. Later, in [this paper](http://www.fmf.uni-lj.si/~mohar/Papers/Torus.pdf) Juvan and Mohar present a polynomial time algorithm that is slightly less difficult to implement.


