{"ID":2824365,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23492","arxiv_id":"2512.23492","title":"Circle graphs can be recognized in linear time","abstract":"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.","short_abstract":"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 decomposit...","url_abs":"https://arxiv.org/abs/2512.23492","url_pdf":"https://arxiv.org/pdf/2512.23492v2","authors":"[\"Christophe Paul\",\"Ignaz Rutter\"]","published":"2025-12-29T14:29:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}