Boxicity of circular arc graphs

DOI10.1007/s00373-010-1002-1zbMath1244.05184arXiv0810.5524OpenAlexW2030164286MaRDI QIDQ659754

Diptendu Bhowmick, L. Sunil Chandran

Publication date: 24 January 2012

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

Full work available at URL: https://arxiv.org/abs/0810.5524

zbMATH Keywords

circular arc graphboxicity

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items

Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Boxicity of line graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Boxicity of leaf powers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Powers of cycles, powers of paths, and distance graphs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• The clique operator on circular-arc graphs
• Hadwiger's conjecture for proper circular arc graphs
• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Interval representations of planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Boxicity and maximum degree
• Structure theorems for some circular-arc graphs
• Boxicity and treewidth
• Unit Circular-Arc Graph Representations and Feasible Circulations
• The Complexity of the Partial Order Dimension Problem
• Stability in circular arc graphs
• Coloring a Family of Circular Arcs
• Interval bigraphs and circular arc graphs