Interval representations of planar graphs. (English) Zbl 0595.05027

Thomassen, Carsten

J. Comb. Theory, Ser. B 40, 9-20 (1986).

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áň

MSC:

05C10

Planar graphs; geometric and topological aspects of graph theory

Keywords:

interval representation; d-dimensional closed interval; intersection graph; planar graph; strict 3-box graph

References:

[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