|
|
| |
| ON THE LINEARITY OF TESTING PLANARITY OF GRAPHS |
| |
Citation： |
Liu Yanpei.ON THE LINEARITY OF TESTING PLANARITY OF GRAPHS[J].Chinese Annals of Mathematics B,1987,8(4):425~434 |
| Page view： 903
Net amount： 649 |
Authors： |
Liu Yanpei; |
|
|
| Abstract： |
In 1978, the author published a paper in which a haracteristic theorem of planarity of a graph was provided as determining if another graph has a fundamental circuit with a certain property. However, the new graph is with, at worst, quadratic order of the verter number of the original graph.
This paper presents a new criterion of testing planarity of a graph based on what the author obtained before. Fortunately, it is equivalent to finding a spanning tree in another graph with only linear order of the verter number of the original one in the worst case. |
Keywords： |
|
Classification： |
|
|
|
Download PDF Full-Text
|
|
|
|
