On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

DOI10.1007/978-3-642-02029-2_15zbMath1194.05130OpenAlexW1646618172MaRDI QIDQ3655149

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

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_15

zbMATH Keywords

bandwidthAT-free graphscocomparability graphsintersection graphscircular-arc graphscubicity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the sphericity and cubicity of graphs
• On the cubicity of certain graphs
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Label placement by maximum independent set in rectangles
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Sphericity, cubicity, and edge clique covers of graphs
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• Domination on Cocomparability Graphs
• On the Cubicity of Interval Graphs
• The Complexity of the Partial Order Dimension Problem
• On the Probable Performance of Heuristics for Bandwidth Minimization
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science