论文标题
图形的弱单元磁盘触点表示无嵌入
Weak Unit Disk Contact Representations for Graphs without Embedding
论文作者
论文摘要
弱单元磁盘触点图是允许代表节点作为内部不相交单元磁盘的集合的图形，如果相应的节点之间有边缘，则边界触摸其界限。在这项工作中，我们专注于图形而无需嵌入，即可以任意选择邻居顺序。我们给出一个线性时间算法，以识别caterpillar是否允许弱单位磁盘触点表示形式，即每个节点与中心路径相邻或在中心路径上。另一方面，我们表明，决定树是否允许这种表示是NP-HARD。
Weak unit disk contact graphs are graphs that admit representing nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. In this work we focus on graphs without embedding, i.e., the neighbor order can be chosen arbitrarily. We give a linear time algorithm to recognize whether a caterpillar, a graph where every node is adjacent to or on a central path, allows a weak unit disk contact representation. On the other hand, we show that it is NP-hard to decide whether a tree allows such a representation.
