Technical Report CS0039

TR#:CS0039
Class:CS
Title: Intersection Graphs Of Curves In The Plane
Authors: G. Ehrlich, S. Even and R. E. Tarjan
PDFCS0039.pdf
Abstract: Let V be a set of curves in the plane. The corresponding intersection graph has V as the set of vertices, and two vertices are connected by an edge if and only if the two corresponding curves intersect in the plane. It is shown that the set of intersection graphs of curves in the plane is a proper subset of the set of all undirected graphs. Furthermore, the set of intersection graphs of straight line-segments is a proper subset of the set of the intersection graphs of curves in the plane. Finally, it is shown that for every k>=3, the problem of determining whether an intesection graph of straight line-segments is k-colorable is NP-complete.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1974/CS/CS0039), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1974
To the main CS technical reports page

Computer science department, Technion
admin