公开(公告)号：US20020118207A1

公开(公告)日：2002-08-29

申请号：US09742231

申请日：2000-12-22

Applicant: NORTEL NETWORKS LIMITED

Inventor： Frank M. Jagla

IPC: G09G005/00

CPC classification number: H04L45/12 ,  H04L45/48

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.

Abstract translation: 用于确定图形平面度的方法和装置利用迭代算法来使用每个链路的循环数来识别曲线图中的无弦周期，并且计算图中每个链路所属的无弦周期数。 无弦循环是可以在没有图形的任何其他连接形成和弦（即穿过循环）的情况下形成的循环。 为了使图形平面，任何链接都不能属于两个以上的无序循环。