Grid intersection graphs and boxicity
type: Item
instance of: scholarly article
title: Grid intersection graphs and boxicity
zbMATH Open document ID: 0784.05031
DOI: 10.1016/0012-365X(93)90354-V
published in: Discrete Mathematics
publication date: 1993-10-24T00:00:00Z
review text: A graph has boxicity \(k\) if \(k\) is the smallest integer such that the graph can be presented as an intersection of parallelepipeds in \(k\)- dimensional space. The bipartite graphs are shown to have boxicity 2. Some inequalities for graphs in higher dimensions are proved.
reviewed by: Vladimir D. Tonchev
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 423563
zbMATH Keywords: grid intersection graphs
zbMATH Keywords: boxicity
zbMATH Keywords: bipartite graphs
author: Stephen J. Bellantoni
author: Irith Ben-Arroyo Hartman
author: Teresa Przytycka
author: Sue Whitesides
MaRDI profile type: Publication
cites work: On grid intersection graphs
cites work: Q5588433
cites work: Computing the boxicity of a graph by covering its complement by cointerval graphs
cites work: Irrepresentability by multiple intersection, or why the interval number is unbounded
cites work: A characterization of Robert's inequality for boxicity
description: scientific article; zbMATH DE number 423563