2 papers
cs.DS2025
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…
cs.DM2025
On a tree-based variant of bandwidth and forbidding simple topological minors
Hugo Jacob, William Lochet, Christophe Paul
We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole () as a topological minor. The corresponding decompositions can be com…