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++ implementation, and I would like to know if there is something similar for toroidal graphs.
$\begingroup$
$\endgroup$
4
asked Jan 21, 2013 at 17:22
-
$\begingroup$ Well, you can check if they dont have as minor one of the 16000 already known obstructions (for not too large graphs, this is less absurd than it sounds...) $\endgroup$– Feldmann DenisCommented Jan 21, 2013 at 21:14
-
$\begingroup$ @FeldmannDenis: Can you give me a reference, please? Although I do think I'd rather use some other method... :) $\endgroup$– Felix GoldbergCommented Jan 21, 2013 at 22:38
-
1$\begingroup$ Perhaps there is something in E. Neufeld, W. Myrvold, Practical toroidality testing, in: 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997, pp. 574–580. Another reference is J. Chambers, Hunting for torus obstructions, M.Sc. Thesis, Department of Computer Science, University of Victoria, 2002 --- I don't know whether that has been published. $\endgroup$– Gerry MyersonCommented Jan 21, 2013 at 22:45
-
$\begingroup$ See also codegolf.stackexchange.com/questions/140514/… $\endgroup$– Licheng ZhangCommented Mar 10, 2023 at 2:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 (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 (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 (2004), describe implementations of this algorithm.
At the other end of the spectrum, in this paper (1995) Juvan, Marincek, and Mohar outline an approach to a linear time toroidality testing algorithm. Later, in this paper Juvan and Mohar present a polynomial time algorithm that is slightly less difficult to implement.
answered Aug 19, 2016 at 4:51