论文标题
是什么使与段和字符串图有关的类难以识别问题？
What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?
论文作者
论文摘要
我们探索什么可以识别特定交叉点定义的类别的原因。我们主要集中在单位网格交点图（UGIG）上，即单位长度对准段和网格相交图的相交图（gigs，它们的定义为没有单位长度限制的UGIG）和字符串图，在平面中的ARC共连接曲线的相互切换图。 我们表明，即使限制了任意大的腰围（即最短循环的长度），探索的图形类是NP-识别的。同样，我们表明，即使对于限制程度的图表，这些类别的识别仍然很难（4、5和8取决于特定类别）。对于Ugigs，我们也提出有关可能表示的大小的结构性结果。
We explore what could make recognition of particular intersection-defined classes hard. We focus mainly on unit grid intersection graphs (UGIGs), i.e., intersection graphs of unit-length axis-aligned segments and grid intersection graphs (GIGs, which are defined like UGIGs without unit-length restriction) and string graphs, intersection graphs of arc-connected curves in a plane. We show that the explored graph classes are NP-hard to recognized even when restricted on graphs with arbitrarily large girth, i.e., length of a shortest cycle. As well, we show that the recognition of these classes remains hard even for graphs with restricted degree (4, 5 and 8 depending on a particular class). For UGIGs we present structural results on the size of a possible representation, too.
