Publication at Faculty of Mathematics and Physics |
2007
Abstract
We provide a polynomial time algorithm for recognition of polygon-circle graphs of girth greater than four, and raise the question if assuming large girth helps recognizing also other types of geometric intersection graphs that are NP-hard in general.