Interval representations of planar graphs. (English) Zbl 0595.05027

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)\).
Reviewer: J.Širáň


05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI


[1] Duchet, P; Hamidoune, Y; Las Vergnas, M; Meyniel, H, Representing a planar graph by vertical lines joining different levels, Discrete math., 46, 221-332, (1983) · Zbl 0516.05023
[2] Melnikov, L.A, ()
[3] Roberts, F, ()
[4] Scheinerman, E.R, Intersection classes and multiple intersection parameters, ()
[5] Scheinerman, E.R; West, D.B, The interval number of a planar graph: three intervals suffice, J. combin. theory ser. B, 35, 224-239, (1983) · Zbl 0528.05053
[6] Thomassen, C, Plane representations of graphs, (), 43-69 · Zbl 0554.05021
[7] Trotter, W.T, Graphs and partially ordered sets, (), 237-268
[8] Ungar, P, On diagrams representing maps, J. London math. soc., 28, 336-342, (1953) · Zbl 0050.18001
[9] West, D.B, Parameters of partial orders and graphs: packing, covering, and representation, () · Zbl 0568.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.