Interval representations of planar graphs
type: Item
instance of: scholarly article
title: Interval representations of planar graphs
zbMATH Open document ID: 0595.05027
DOI: 10.1016/0095-8956(86)90061-4
author: Carsten Thomassen
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 3957135
zbMATH Keywords: interval representation
zbMATH Keywords: d-dimensional closed interval
zbMATH Keywords: intersection graph
zbMATH Keywords: planar graph
zbMATH Keywords: strict 3-box graph
reviewed by: Jozef Širáň
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90061-4
OpenAlex ID: W1971244706
cites work: Representing a planar graph by vertical lines joining different levels
cites work: Q4138414
cites work: The interval number of a planar graph: Three intervals suffice
cites work: Q3216670
cites work: Q3672006
cites work: On Diagrams Representing Maps
cites work: Q3684157
description: scientific article; zbMATH DE number 3957135