A Practical Algorithm for Embedding Graphs on Torus

Abstract

Embedding graphs on the torus is a problem with both theoretical and practical importance. It is required to embed a graph on the torus for solving many application problems such as VLSI design, graph drawing and so on. Polynomial time and exponential time algorithms for embedding graphs on the torus are known. However, the polynomial time algorithms are very complex and their implementation has been a challenge for a long time. On the other hand, the implementations of some exponential time algorithms are known but they are not efficient for large graphs in practice. To develop an efficient practical tool for embedding graphs on the torus, we propose a new exponential time algorithm for embedding graphs on the torus. Compared with a well used previous exponential time algorithm, our algorithm has a better practical running time.