Boxicity and treewidth

DOI10.1016/J.JCTB.2006.12.004zbMath1121.05091arXivmath/0505544OpenAlexW2034198559MaRDI QIDQ2642011

Naveen Sivadasan, L. Sunil Chandran

Publication date: 20 August 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

treewidthintersection graphsgraph classesboxicity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (36)

Structural parameterizations for boxicity ⋮ Separation dimension of graphs and hypergraphs ⋮ Boxicity of graphs on surfaces ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Boxicity and treewidth ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Product dimension of forests and bounded treewidth graphs ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ On the Cubicity of Interval Graphs ⋮ Boxicity of line graphs ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ On the boxicity of Kneser graphs and complements of line graphs ⋮ Intersection dimension and graph invariants ⋮ Boxicity of leaf powers ⋮ Chordal bipartite graphs with high boxicity ⋮ Boxicity of circular arc graphs ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Boxicity and topological invariants ⋮ Boxicity and maximum degree ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ Treewidth computations. II. Lower bounds ⋮ A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\) ⋮ Cubicity, degeneracy, and crossing number ⋮ The cubicity of hypercube graphs ⋮ Representing graphs as the intersection of cographs and threshold graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Better bounds for poset dimension and boxicity ⋮ Boxicity of graphs with bounded degree ⋮ Cubicity, boxicity, and vertex cover ⋮ An upper bound for cubicity in terms of boxicity ⋮ Boxicity of Halin graphs ⋮ Bounds for the boxicity of Mycielski graphs ⋮ On the stab number of rectangle intersection graphs ⋮ On the cubicity of interval graphs ⋮ Lower bounds for boxicity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Grid intersection graphs and boxicity
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Interval representations of planar graphs
• Poset boxicity of graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A note on circular dimension
• Optimal packing and covering in the plane are NP-complete
• The circular dimension of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Treewidth for graphs with small chordality
• Graph minors. XIII: The disjoint paths problem
• Boxicity and treewidth
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• The Complexity of the Partial Order Dimension Problem
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Graph Classes: A Survey
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Tree-width and circumference of graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Boxicity and treewidth