Computing the boxicity of a graph by covering its complement by cointerval graphs

DOI10.1016/0166-218X(83)90077-XzbMath0524.05059MaRDI QIDQ585228

Fred S. Roberts, Margaret B. Cozzens

Publication date: 1983

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

zbMATH Keywords

intersection graph; interval graph; boxicity; edge coverings

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C99: Graph theory

Related Items

On the Computation of the Competition Number of a Graph, Grid intersection graphs and boxicity, The relationship between the threshold dimension of split graphs and various dimensional parameters, The cubicity of hypercube graphs, Boxicity of graphs with bounded degree, Cubicity, boxicity, and vertex cover, An upper bound for cubicity in terms of boxicity, On the cubicity of certain graphs, Irrepresentability by multiple intersection, or why the interval number is unbounded, On dimensional properties of graphs, Representations of graphs and networks (coding, layouts and embeddings), Intersection dimensions of graph classes, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs, Boxicity and maximum degree, Boxicity and treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chronological orderings of interval graphs
• A characterization of Robert's inequality for boxicity
• On intersections of interval graphs
• The splittance of a graph
• Parallel concepts in graph theory
• Incidence matrices and interval graphs
• Intransitive indifference with unequal indifference intervals
• Representation of a finite graph by a set of intervals on the real line
• Counting Interval Graphs
• A Characterization of Comparability Graphs and of Interval Graphs