Touching graphs of unit balls
| 详细信息 | 推荐本文 | |
- 作者：Petr Hlin臎n媒
- 刊名：Lecture Notes in Computer Science
- 出版时间：1997
- 出版年：1997
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：1353
- 期：1
- 页码：350-358
- 数据来源：sp
摘要
The touching graph of balls is a graph that admits a representation by non-intersecting balls in the space (of prescribed dimension), so that its edges correspond to touching pairs of balls. By a classical result of Koebe [5], the disc touching graphs are exactly the planar graphs. This paper deals with a recognition of unit-ball touching graphs. The 2-dimensional case was proved to be NP-hard by Breu and Kirkpatrick [1]. We show in this paper that also unit-ball touching graphs in dimensions 3 and 4 are NP-hard to recognize. By a recent result of Kirkpatrick and Rote, these results may be transferred in ball-touching graphs in one dimension higher.