Grid intersection graphs and boxicity
From MaRDI portal
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.
Recommendations
Cites work
- A characterization of Robert's inequality for boxicity
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- scientific article; zbMATH DE number 3307331 (Why is no real title available?)
- Irrepresentability by multiple intersection, or why the interval number is unbounded
- On grid intersection graphs
Cited in
(39)- An upper bound for cubicity in terms of boxicity
- Boxicity of Halin graphs
- On the cubicity of certain graphs
- On the cubicity of interval graphs
- Covering with Euclidean boxes
- On grid intersection graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- Intersection dimensions of graph classes
- Characterization of the graphs with boxicity \(\leq 2\)
- Lower bounds for boxicity
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Boxicity and treewidth
- On the boxicity of Kneser graphs and complements of line graphs
- String graphs of k-bend paths on a grid
- Ferrers dimension of grid intersection graphs
- The frame dimension and the complete overlap dimension of a graph
- scientific article; zbMATH DE number 4023340 (Why is no real title available?)
- scientific article; zbMATH DE number 1472165 (Why is no real title available?)
- Optimal grid representations
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
- Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
- Intersection dimension of bipartite graphs
- scientific article; zbMATH DE number 5214885 (Why is no real title available?)
- Separability, boxicity, and partial orders
- Functionality of box intersection graphs
- Chordal bipartite graphs with high boxicity
- Simultaneous contact representations of planar graphs
- A survey on the boxicity and cubicity of graphs
- Grid intersection graphs and order dimension
- Segment intersection representations, level planarity and constrained ordering problems
- On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers
- A constant factor approximation algorithm for boxicity of circular arc graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- On orthogonal ray trees
- The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing
- Boxicity and cubicity of asteroidal triple free graphs
- On the cubicity of bipartite graphs
- The cubicity of hypercube graphs
This page was built for publication: Grid intersection graphs and boxicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685652)
