Wagner's theorem for Torus graphs |
| |
Authors: | AK Dewdney |
| |
Institution: | Computer Science Department, University of Western Ontario, London, Ontario, Canada |
| |
Abstract: | Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|