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 (3)

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

This page was built for publication: On the cubicity of interval graphs