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 , pp. 350-358(Official URL:

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 [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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_80
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar

Actions (login required)

View Item View Item