Generating planar 4-connected graphs |
| |
Authors: | David Barnette |
| |
Affiliation: | (1) University of California, Davis, California, U.S.A. |
| |
Abstract: | In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG 0,G 1, …,G n such thatG 0 is the graph of the cube,G n=G, and each graph is obtained from its predecessor by one of our three operations. Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|