We show that it is NP-hard to recognize intersection graphs of homothetic convex polygons in a plane with a given fixed shape. The article incorporates a structural result for partial 3-trees. Namely we show that every partial planar 3-tree has a homothetic representation.
We show that it is NP-hard to recognize intersection graphs of homothetic convex polygons in a plane with a given fixed shape. The article incorporates a structural result for partial 3-trees. Namely we show that every partial planar 3-tree has a homothetic representation. (en)