Better bounds for poset dimension and boxicity

DOI10.1090/TRAN/7962zbMath1433.05233arXiv1804.03271OpenAlexW3103128284WikidataQ127205713 ScholiaQ127205713MaRDI QIDQ5217895

David R. Wood, Alexander D. Scott

Publication date: 26 February 2020

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Euler genusmaximum boxicity of graphs

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items (14)

Local boxicity ⋮ Clustered 3-colouring graphs of bounded degree ⋮ The micro-world of cographs ⋮ Adjacency posets of outerplanar graphs ⋮ Local boxicity and maximum degree ⋮ Separating layered treewidth and row treewidth ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ On the boxicity of Kneser graphs and complements of line graphs ⋮ Random bipartite posets and extremal problems ⋮ The order dimension of divisibility ⋮ Boxicity, poset dimension, and excluded minors ⋮ The graph of critical pairs of a crown ⋮ Fractional local dimension ⋮ Separation dimension and degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minors and dimension
• Boxicity and topological invariants
• Constructions and nonexistence results for suitable sets of permutations
• Box representations of embedded graphs
• Boxicity, poset dimension, and excluded minors
• Boxicity of graphs with bounded degree
• Interval representations of planar graphs
• On the dimensions of ordered sets of bounded degree
• A characterization of Robert's inequality for boxicity
• Graphs drawn with few crossings per edge
• A partial k-arboretum of graphs with bounded treewidth
• Colouring a graph frugally
• Sparsity and dimension
• Track layouts, layered path decompositions, and leveled planarity
• On the order dimension of 1-sets versus \(k\)-sets
• Nowhere dense graph classes and dimension
• Boxicity of graphs on surfaces
• Tree-width and dimension
• An annotated bibliography on 1-planarity
• Layered separators in minor-closed graph classes with applications
• On the dimension of posets with cover graphs of treewidth 2
• Boxicity and maximum degree
• Cubicity, degeneracy, and crossing number
• Dimension and height for posets with planar cover graphs.
• Boxicity and treewidth
• Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions
• Parameters Tied to Treewidth
• Map graphs
• On a Coloring Problem.
• Suitable Permutations, Binary Covering Arrays, and Paley Matrices
• New bounds on the edge number of ak-map graph
• The dimension of random ordered sets
• Topological Minors of Cover Graphs and Dimension
• Planar Posets Have Dimension at Most Linear in Their Height
• Structure of Graphs with Locally Restricted Crossings
• Contact representations of planar graphs with cubes
• Minimal scrambling sets of simple orders
• Concerning a Certain Set of Arrangements
• Boxicity and Poset Dimension

This page was built for publication: Better bounds for poset dimension and boxicity