Interval representations of planar graphs (Q1077425)
From MaRDI portal
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
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