| 摘要 |
A method and apparatus for determining graph planarity makes use of an iterative algorithm to identify the chordless cycles in a graph and count, using a cyclic number for each link, the number of chordless cycles to which each link of the graph belongs. Chordless cycles are those cycles which can be formed without any other links of the graph forming a chord (i.e. crossing through the cycle). In order for a graph to be planar, any link cannot belong to more than two chordless cycles.
|
