Circle graphs can be recognized in linear time
By: Christophe Paul, Ignaz Rutter
To date, the best circle graph recognition algorithm runs in almost linear time as it relies on a split decomposition algorithm that uses the union-find data-structure. We show that in the case of circle graphs, the PC-tree data-structure 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.
Similar Papers
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Data Structures and Algorithms
Colors circle graphs with three colors.
Efficient recognition algorithms for $(1,2)$-, $(2,1)$- and $(2,2)$-graphs
Discrete Mathematics
Makes computers sort special pictures faster.
A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Data Structures and Algorithms
Simplifies complex networks for faster computer analysis.