| Article ID: | iaor20011981 |
| Country: | Japan |
| Volume: | E83-A |
| Issue: | 4 |
| Start Page Number: | 627 |
| End Page Number: | 638 |
| Publication Date: | Apr 2000 |
| Journal: | Transactions of the Institute of Electronics, Information and Communication Engineers |
| Authors: | Sugihara Kokichi, Hiroshima Tetsuya, Miyamoto Yuichiro |
| Keywords: | combinatorial analysis, graphs |
This paper presents an algorithm to judge whether a given graph is homeomorphic to some Delaunay graph. The problem is reduced to a certain type of linear programming, and here can be solved in polynomial time. This algorithm and its induction is simpler than another algorithm for the same problem proposed independently at almost the same time. The algorithm is applied to an experimental study for the distribution of Delaunay graphs among all triangulation graphs.