论文标题
关于识别棍棒，biphook和max耐耐能图的复杂性
On the complexity of recognizing Stick, BipHook and Max Point-Tolerance graphs
论文作者
论文摘要
棍子图定义如下。令A（分别为b）为平面中的一组垂直（分别是水平）段，以使B中的片段的底部端点和B中的段的左端点位于与斜率-1的同一地面直线上。由a和b定义的棒图（必然是二分）是A中与B中的段中的段的相交图。我们通过证明识别棍子图是NP完整的，回答了一个空旷的问题。这个结果使我们可以轻松解决其他两个开放问题，即识别biphook图和最大点耐受性图。我们表明，这两个都是NP完整问题。
Stick graphs are defined as follows. Let A (respectively B) be a set of vertical (respectively horizontal) segments in the plane such that the bottom endpoints of the segments in A and the left endpoints of the segments in B lie on the same ground straight line with slope -1. The Stick graph defined by A and B, which is necessarily bipartite, is the intersection graph of the segments in A with the segments in B. We answer an open problem by showing that recognizing Stick graphs is NP-complete. This result allows us to easily solve two other open problems, namely the recognition of BipHook graphs and of max point-tolerance graphs. We show that both of them are NP-complete problems.
