Touching Graphs of Unit Balls
Hliněný, Petr (1998) Touching Graphs of Unit Balls. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 350-358 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_80).
Full text not available from this repository.
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 , 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 . 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.
Repository Staff Only: item control page