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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references