Cubicity, degeneracy, and crossing number

DOI10.1016/j.ejc.2013.06.021zbMath1296.05138OpenAlexW2143378820MaRDI QIDQ2509731

Abhijin Adiga, Rogers Mathew, L. Sunil Chandran

Publication date: 29 July 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3342/

zbMATH Keywords

intersection graph\(k\)-degenerate graphboxicity of a graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ Boxicity and topological invariants ⋮ Better bounds for poset dimension and boxicity

Cites Work

• Unnamed Item
• Unnamed Item
• Boxicity of line 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
• Boxicity of graphs with bounded degree
• An upper bound for cubicity in terms of boxicity
• Interval representations of planar graphs
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Graphs drawn with few crossings per edge
• A special planar satisfiability problem and a consequence of its NP- completeness
• Cubicity and bandwidth
• Boxicity and maximum degree
• Sphericity, cubicity, and edge clique covers of graphs
• Boxicity and treewidth
• Extremal Combinatorics
• The Complexity of the Partial Order Dimension Problem
• The dimension of random ordered sets
• Probability and Computing
• Boxicity and Poset Dimension