Intersection Graphs of Segments

✍ Scribed by J. Kratochvil; J. Matousek

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 998 KB
• Volume: 62
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1071

✦ Synopsis

Intersection graphs of segments (the class SEG) and of other simple geometric 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. Among others, we prove that the recognition of SEG-graphs is of the same complexity as the decision of solvability of a system of strict polynomial inequalities in the reals, i.e., as the decision of a special existentially quantified sentence in the theory of real closed fields, and thus it belongs to PSPACE. If the segments of the representation are restricted to lie in a fixed number ( (k) ) of directions, we show that the corresponding recognition problem is NP-complete for every (k \geqslant 2). As for the size of representations, we show that the description of any segment representation, specifying the coordinates of the endpoints, may require exponential number of digits for certain (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 larger graph whose each segment representation contains a homeomorphic copy of (R . \quad C 1994) Academic Press. Inc.