Grid intersection graphs and boxicity

DOI10.1016/0012-365X(93)90354-VzbMath0784.05031MaRDI QIDQ685652

Teresa M. Przytycka, Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, S. H. Whitesides

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphsboxicitygrid intersection graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99)

Related Items (20)

A special planar satisfiability problem and a consequence of its NP- completeness ⋮ Intersection dimensions of graph classes ⋮ On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Boxicity and treewidth ⋮ Ferrers dimension of grid intersection graphs ⋮ Separability, boxicity, and partial orders ⋮ On orthogonal ray trees ⋮ Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs ⋮ The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing ⋮ Optimal grid representations ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ On the cubicity of bipartite graphs ⋮ The cubicity of hypercube graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ An upper bound for cubicity in terms of boxicity ⋮ String graphs of k-bend paths on a grid ⋮ On the cubicity of certain graphs ⋮ On the cubicity of interval graphs ⋮ Lower bounds for boxicity

Cites Work

• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Irrepresentability by multiple intersection, or why the interval number is unbounded
• A characterization of Robert's inequality for boxicity
• On grid intersection graphs

This page was built for publication: Grid intersection graphs and boxicity