On the cubicity of interval graphs

DOI10.1007/s00373-008-0830-8zbMath1188.05091OpenAlexW2136836331MaRDI QIDQ1043802

Naveen Sivadasan, L. Sunil Chandran, Mathew C. Francis

Publication date: 9 December 2009

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

Full work available at URL: https://doi.org/10.1007/s00373-008-0830-8

zbMATH Keywords

interval graphmaximum degreecubicity\(k\)-cube representation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Cubicity of interval graphs and the claw number ⋮ Cubicity of Interval Graphs and the Claw Number

Cites Work

• Unnamed Item
• Unnamed Item
• Grid intersection graphs and boxicity
• On the sphericity and cubicity of graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• The cubicity of hypercube graphs
• An upper bound for cubicity in terms of boxicity
• On the cubicity of certain graphs
• Interval representations of planar graphs
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Poset boxicity of graphs
• A note on circular dimension
• The circular dimension of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Boxicity and maximum degree
• Sphericity, cubicity, and edge clique covers of graphs
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem