String Graph Obstacles of High Girth and of Bounded Degree

Maria Chudnovsky, David Eppstein, David Fischer

A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…