On the Cubicity of AT-Free Graphs and Circular-Arc Graphs
From MaRDI portal
Publication:3655149
DOI10.1007/978-3-642-02029-2_15zbMath1194.05130MaRDI 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
bandwidth; AT-free graphs; cocomparability graphs; intersection graphs; circular-arc graphs; cubicity
68Q25: Analysis of algorithms and problem complexity
05C75: Structural characterization of families of graphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
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