论文标题
识别具有弱单元磁盘接触表示的嵌入式毛毛虫是NP-HARD
Recognizing embedded caterpillars with weak unit disk contact representations is NP-hard
论文作者
论文摘要
弱单元磁盘触点图是将节点表示表示为内部不相交单元磁盘的集合的图形，如果相应的节点之间有边缘，则边界触摸其界限。我们提供基于小工具的减少，以表明识别嵌入式毛毛虫接受弱单位磁盘接触表示为NP-HARD。
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. We provide a gadget-based reduction to show that recognizing embedded caterpillars that admit a weak unit disk contact representation is NP-hard.
