Grid intersection graphs and boxicity

DOI10.1016/0012-365X(93)90354-VzbMATH Open0784.05031MaRDI QIDQ685652FDOQ685652

Teresa Przytycka, Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Sue Whitesides

Publication date: 24 October 1993

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

Recommendations

• Cubicity, boxicity, and vertex cover
• Boxicity and maximum degree
• Chordal bipartite graphs with high boxicity
• Boxicity of graphs with bounded degree
• Geometric Representation of Graphs in Low Dimension

zbMATH Keywords

bipartite graphsboxicitygrid intersection graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On grid intersection graphs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• A characterization of Robert's inequality for boxicity
• Irrepresentability by multiple intersection, or why the interval number is unbounded

Cited In (29)

• String graphs of \(k\)-bend paths on a grid
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• The frame dimension and the complete overlap dimension of a graph
• Title not available (Why is that?)
• Geometric representation of graphs in low dimension using axis parallel boxes
• Boxicity and cubicity of asteroidal triple free graphs
• The cubicity of hypercube graphs
• On the cubicity of bipartite graphs
• Title not available (Why is that?)
• Lower bounds for boxicity
• Covering with Euclidean boxes
• Separability, boxicity, and partial orders
• A special planar satisfiability problem and a consequence of its NP- completeness
• An upper bound for cubicity in terms of boxicity
• Optimal grid representations
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Title not available (Why is that?)
• Ferrers dimension of grid intersection graphs
• Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
• On orthogonal ray trees
• The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing
• On the cubicity of interval graphs
• On the boxicity of Kneser graphs and complements of line graphs
• Boxicity and treewidth
• On grid intersection graphs
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Intersection dimensions of graph classes
• A constant factor approximation algorithm for boxicity of circular arc graphs
• On the cubicity of certain 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)