Method and apparatus for determining graph planarity
AssigneeNortel Networks Limited
InventorFrank M. Jagla
Life of this patent
Estimating the term…
Abstract
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.
Claims20
A method for use in determining planarity of a graph comprising:
- determining the number of chordless cycles to which each link of the graph belongs;
- and
- evaluating whether the number of chordless cycles for said each link is less than or equal to two.
A method for use in determining planarity of a graph, comprising:
- selecting a base vertex of the graph;
- constructing a minimum distance directed spanning tree from said base vertex;
- determining a cut tree of said spanning tree, said cut tree comprising at least one cut tree link;
- and
- determining if there are any cycles composed of cut tree links.
A method for use in determining planarity of a graph, comprising:
- selecting a base vertex of the graph;
- constructing a minimum distance directed spanning tree from said base vertex;
- determining a cut tree of said spanning tree, said cut tree comprising at least one cut tree link;
- identifying cycles related to said at least one cut tree link and said base vertex;
- identifying chordless cycles from amongst said identified cycles;
- incrementing a cyclic number for each link appearing in each of said chordless cycles;
- and
- evaluating whether the number of chordless cycles for each link exceeds two, and if so, determining that said graph is non-planar.
A method for determining planarity of a graph comprising:
- repetitively, until there are no remaining vertices or links of the graph:
- selecting a vertex as a base vertex;
- constructing a minimum-distance directed spanning tree from said base vertex;
- defining a cut tree of the directed spanning tree;
- identifying cut tree links related to said base vertex;
- determining if any of said identified cut tree links form a cut tree cycle, and if so, determining if there is a persistent cut tree cycle, and if so, determining that the graph is non-planar;
- identifying chordless cycles for said identified cut tree links;
- incrementing a cyclic number for each link in said chordless cycles and determining that the graph is non-planar if the cyclic number of any link exceeds two;
- removing vertices having (vertex degree) minus (number of attached links in chordless cycles) equal to 0;
- and selecting a new base vertex from any vertices remaining in the graph.
A computer readable medium containing computer executable code for determining planarity of a graph which adapts a computer to:
- determine the number of chordless cycles to which each link of the graph belongs;
- and
- evaluate whether the number of chordless cycles for said each link is less than or equal to two.
A computer readable medium containing computer executable code for determining planarity of a graph which adapts a computer to:
- select a base vertex of the graph;
- construct a minimum distance directed spanning tree from said base vertex;
- obtain a cut tree of said spanning tree, said cut tree comprising at least one cut tree link;
- and
- determine if there are any cycles composed of cut tree links.
An apparatus for determining planarity of a graph comprising:
- an input device for inputting said graph;
- a computer;
- an output device for outputting a planarity result;
- wherein said computer is adapted to:
- determine the number of chordless cycles to which each link of the graph belongs;
- and
- evaluate whether the number of chordless cycles for said each link is less than or equal to two, indicating planarity.
Dependencies are inferred from the claim text.