| A NEW APPROACH TO THE LINEARITY OF TESTING PLANARITY OF GRAPHS |
| |
| 作者姓名： | 刘彦佩 |
| |
| 作者单位： | Institute of |
| |
| 基金项目： | This was a report invited by RUTCOR, The State University of New Jersey, Rutgers, U. S. A. in1984，the main part of this paper was completed during the author's stay at the Department of C & O,University of Waterloo, Canada . |
| |
| 摘 要： | In testing planarity of graphs,there are many criteria.The earliest one as known is the Kuratowski's theorem,then Whitney's,Maclane's, and so forth.Since the early sixties,people have begun researches on algorithms.Up to 1974,Hopcroft and Tarjan found an algorithm with a computing time being a linear function of the order of a graph.This is the linearity concerned here.This paper presents a new approach to the linearity by means of transforming the problem of testing planarity of a graph G into that of finding a spanning tree on another graph H,called an auxiliary graph of G,with the order of H being a linear function of that of G.And moreover,we can also make the size of H be a linear function of that of G.The whole procedure is based on the building up of a theory of linear equations on GF(2)related to G.
|
| 本文献已被 CNKI 等数据库收录！ |
|
