Intersection graphs of segments (Q1338319)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intersection graphs of segments |
scientific article |
Statements
Intersection graphs of segments (English)
0 references
5 January 1995
0 references
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 \geq 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\).
0 references
intersection graphs
0 references
segments
0 references
membership problem
0 references
recognition
0 references
SEG- graphs
0 references
complexity
0 references
polynomial inequalities
0 references
decision
0 references
recognition problem
0 references
NP-complete
0 references
segment representation
0 references