.png){kind=icon}
.png){kind=icon}
Return
Circle Graphs Can Be Recognized in Linear Time
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.72.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
To date, the best circle graph recognition algorithm, due to Gioan et al. [19] runs in almost linear time as it relies on a split decomposition algorithm [20] that uses the union-find data-structure [16, 34]. We show that in the case of circle graphs, the PC-tree data-structure [31] allows one to avoid the union-find data-structure to compute the split decomposition in linear time. As a consequence, we obtain the first linear-time recognition algorithm for circle graphs.
Keywords:
graph classes
circle graphs
graph algorithms
Journal
4
IF:
0
Papers:
81
Citations:
0