Touching Graphs of Unit Balls

Hlinený, 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.

Abstract

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
ID Code:134

Repository Staff Only: item control page

References

H. Breu, D.G. Kirkpatrick, On the compexity of recognizing intersection and touching graphs of discs, In: Graph Drawing (F.J. Brandenburg ed.), Proceedings Graph Drawing '95, Passau, September 1995, Lecture Notes in Computer Science 1027, Springer Verlag 1996, 88-98.

H. de Fraysseix, P.O. de Mendez, P. Rosenstiehl, On triangle contact graphs, Combinatorics, Probability and Computing 3 (1994), 233-246.

M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman and Company, New York 1978.

P. Hlineny, Contact graphs of curves (extended abstract), In: Graph Drawing (F.J. Brandenburg ed.), Proceedings Graph Drawing '95, Passau, September 1995, Lecture Notes in Computer Science 1027, Springer Verlag 1996, 312-323.

P. Koebe, Kontaktprobleme der konformen Abbildung, Berichte über die Verhandlungen der Sächsischen, Akad. d. Wiss., Math.-Physische Klasse 88 (1936), 141-164.

J. Kratochvíl, Intersection graphs of noncrossing arc-connected sets in the plane, Proceedings Graph Drawing '96, Berkeley, September 1996, Lecture Notes in Computer Science 1190, Springer Verlag, Berlin Heidelberg 1997.

C.B. Lekkerkerker, J.C. Boland, Representation of finite graphs by a set of intervals on the real line, Fund. Math. 51 (1962), 45-64.