A constant factor approximation algorithm for boxicity of circular arc graphs

DOI10.1016/j.dam.2014.06.013zbMath1300.05188OpenAlexW2055852904MaRDI QIDQ741528

L. Sunil Chandran, Abhijin Adiga, Jasine Babu

Publication date: 12 September 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.013

zbMATH Keywords

approximation algorithmboxicitycircular arc graphscubicitynormal circular arc graphs

Mathematics Subject Classification ID

Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On orthogonal ray graphs
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Grid intersection graphs and boxicity
• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• An upper bound for cubicity in terms of boxicity
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Interval representations of planar graphs
• A characterization of Robert's inequality for boxicity
• On the complexity of the k-chain subgraph cover problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Linear-time recognition of circular-arc graphs
• Finding a maximum induced matching in weakly chordal graphs
• A min-max property of chordal bipartite graphs with applications
• New results on induced matchings
• List homomorphisms and circular arc graphs
• Characterization of the graphs with boxicity \(\leq 2\)
• Matrix characterizations of circular-arc graphs
• Structure theorems for some circular-arc graphs
• Boxicity and treewidth
• Pathwidth of Circular-Arc Graphs
• The Branch-Width of Circular-Arc Graphs
• The Complexity of the Partial Order Dimension Problem
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Treewidth of Circular-Arc Graphs
• Contact representations of planar graphs with cubes
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Boxicity and Poset Dimension