RECOGNITION OF CIRCLE GRAPHS

被引：73

作者：

SPINRAD, J

机构：

[1] Department of Computer Science, Vanderbilt University, Nashville

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1994年 / 16卷 / 02期

关键词：

D O I：

10.1006/jagm.1994.1012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a new algorithm for recognizing circle graphs, combining ideas from an earlier circle graph recognition algorithm due to Gabor, Hsu, and Supowit and an algorithm to determine whether a graph can be decomposed by the split decomposition. The result is an O(n2) algorithm for placing chords on the circle when the split decomposition is known. When combined with the result of the companion paper, this gives an O(n2) algorithm for circle graph recognition. © 1994 Academic Press, Inc.

引用

页码：264 / 282

页数：19

共 14 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].