Contact Graphs of Curves

Hliněný, Petr (1996) Contact Graphs of Curves. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995 , pp. 312-323(Official URL:

Full text not available from this repository.


Contact graphs are a special kind of intersection graphs of geometrical objects in which we do not allow the objects to cross but only to touch each other. Contact graphs of simple curves (and line segments as a special case) in the plane are considered. Several classes of contact graphs are introduced and their properties and inclusions between them are studied. Also the relation between planar and contact graphs is mentioned. Finally, it is proved that the recognition of contact graphs of curves (line segments) is NP-complete (NP-hard) even for planar graphs.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021814
Classifications: Z Theory > Z.250 Geometry
M Methods > M.600 Planar
G Algorithms and Complexity > G.560 Geometry

Actions (login required)

View Item View Item