Contact graphs of line segments are NP-complete (Q5937922)
From MaRDI portal
scientific article; zbMATH DE number 1621231
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Contact graphs of line segments are NP-complete |
scientific article; zbMATH DE number 1621231 |
Statements
Contact graphs of line segments are NP-complete (English)
0 references
29 March 2002
0 references
Contact graphs of line segments are intersection graphs of a family of line segments in the plane such that every two distinct line segments in the family have no common interior point. By reducing PLANAR 3-SAT, the author proves that the recognition problem of contact graphs of line segments is NP-complete, even for planar graphs.
0 references
contact graph
0 references
intersection graph
0 references
NP-completeness
0 references
recognition problem
0 references
