On unit grid intersection graphs and several other intersection graph classes

Abstrakt

The article answers several questions about recognition of particular graph classes where the graphs are as sparse as possible. Among other results, it solves the question of Kratochvíl and Pergel from 2008 about recognition of string-graphs with arbitrarily large girth.

Klíčová slova

• unit
• grid
• graphs
• several
• other
• intersection
• graph
• classes