Circle graphs can be recognized in linear time

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 tha…