Menus of kuratowski subgraphs |
| |
Authors: | Sue O. Hart S. Gill Williamson |
| |
Affiliation: | a University of California, San Diego, La Jolla, California |
| |
Abstract: | Motivated by heuristic embedding algorithms, this paper is concerned with the organization of potentially large lists of Kuratowski subgraphs of an arbitrary nonpianar graph. A graphical structure called a "nearly Hamiltonian" graph is defined. It is shown that lists of Kuralowski subgraphs can be lexicographically organized in such structures. It is shown that any nonpianar graph contains such structures and at least one such structure with a nonempty list of Kuratowski subgraphs can be located in linear time in ihe edges of the graph. |
| |
Keywords: | |
本文献已被 InformaWorld 等数据库收录! |