INTERSECTION GRAPHS OF SEGMENTS

Intersection graphs of segments (the class SEG) and of other simple ge ometric objects in the plane are considered. The results fall into two main areas: how difficult is the membership problem for a given class and how large are the pictures needed to draw the representations. Am ong others, we prove that the recognition of SEG-graphs is of the same complexity as the decision of solvability of a system of strict polyn omial inequalities in the reals, i.e., as the decision of a special ex istentially quantified sentence in the theory of real closed fields, a nd thus it belongs to PSPACE. If the segments of the representation ar e restricted to lie in a fixed number (k) of directions, we show that the corresponding recognition problem is NP-complete for every k great er than or equal to 2. As for the size of representations, we show tha t the description of any segment representation, specifying the coordi nates of the endpoints, may require exponential number of digits for c ertain n-vertex graphs. One of our main tools is a lemma, saying that given a representation R of a graph by segments, one may construct a l arger graph whose each segment representation contains a homeomorphic copy of R. (C) 1994 Academic Press, Inc.