Abstract :
Contact graphs are a special kind of intersection graphs of geometrical objects in which the objects are not allowed to cross but only to touch each other. Contact graphs of line segments in the plane are considered — it is proved that recognizing line-segment contact graphs, with contact degrees of 3 or more, is an NP-complete problem, even for planar graphs. This result contributes to the related research on recognition complexity of curve contact graphs (Hliněný J. Combin. Theory Ser. B 74 (1998) 87).
