Interval representations of planar graphs (Q1077425): Difference between revisions

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)\).