Chordal bipartite graphs with high boxicity

DOI10.1007/s00373-011-1017-2zbMath1235.05096arXiv0906.0541MaRDI QIDQ659714

L. Sunil Chandran, Rogers Mathew, Mathew C. Francis

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0906.0541

zbMATH Keywords

interval graphs; boxicity; chordal bipartite graphs; grid intersection graphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Bounds for the boxicity of Mycielski graphs, Boxicity of line graphs, On orthogonal ray graphs, Structural properties of word representable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• Characterizations of strongly chordal graphs
• Interval representations of planar graphs
• On grid intersection graphs
• Classes of bipartite graphs related to chordal graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Boxicity and maximum degree
• Boxicity and treewidth
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey