Title of article
Contact graphs of line segments are NP-complete Original Research Article
Author/Authors
Petr Hlin?n?، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
12
From page
95
To page
106
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).
Journal title
Discrete Mathematics
Serial Year
2001
Journal title
Discrete Mathematics
Record number
949690
Link To Document