Circle graphs can be recognized in linear time
By: Christophe Paul, Ignaz Rutter
Potential Business Impact:
Finds circle shapes in computer data faster.
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
Circle graphs can be recognized in linear time
Data Structures and Algorithms
Finds circle patterns in data much faster.
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.