Interval representations of planar graphs (Q1077425)

From MaRDI portal
Revision as of 00:25, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Interval representations of planar graphs
scientific article

    Statements

    Interval representations of planar graphs (English)
    0 references
    0 references
    1986
    0 references
    A graph is said to be a strict d-box graph if it is an intersection graph such that the sets are closed d-boxes \((=d\)-dimensional closed intervals) in \(R^ d\), no two of which have an interior point in common and such that two boxes which intersect have precisely a (d-1)-box in common. The author proves that every planar graph is a strict 3-box graph, and characterizes the 2-box graphs; these turn out to be precisely the proper subgraphs of 4-connected planar triangulations. In the case when more than one rectangle is allowed to represent a vertex, the author shows that two rectangles for each vertex are sufficient to represent any planar graph \((d=2)\).
    0 references
    interval representation
    0 references
    d-dimensional closed interval
    0 references
    intersection graph
    0 references
    planar graph
    0 references
    strict 3-box graph
    0 references

    Identifiers