Better bounds for poset dimension and boxicity

DOI10.1090/TRAN/7962MaRDI QIDQ5217895zbMATH OpenOpenAlexWikidataFDO

Authors David R. Wood, Alex 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

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

Abstract: We prove that the dimension of every poset whose comparability graph has maximum degree $Delta$ is at most $Deltalo{g}^{1+o(1)}Delta$. This result improves on a 30-year old bound of F"uredi and Kahn, and is within a $lo{g}^{o(1)}Delta$ factor of optimal. We prove this result via the notion of boxicity. The "boxicity" of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $Delta$ has boxicity at most $Deltalo{g}^{1+o(1)}Delta$, which is also within a $lo{g}^{o(1)}Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $Theta(sqrtglogg)$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor.

Recommendations

• Boxicity and maximum degree
• Boxicity of graphs with bounded degree
• Poset boxicity of graphs

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1161251 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A characterization of Robert's inequality for boxicity
• A partial k-arboretum of graphs with bounded treewidth
• An annotated bibliography on 1-planarity
• Box representations of embedded graphs
• Boxicity and maximum degree
• Boxicity and topological invariants
• Boxicity and treewidth
• Boxicity of graphs on surfaces
• Boxicity of graphs with bounded degree
• Boxicity, poset dimension, and excluded minors
• Colouring a graph frugally
• Concerning a Certain Set of Arrangements
• Constructions and nonexistence results for suitable sets of permutations
• Contact representations of planar graphs with cubes
• Cubicity, degeneracy, and crossing number
• Dimension and height for posets with planar cover graphs.
• Graphs drawn with few crossings per edge
• Interval representations of planar graphs
• Layered separators in minor-closed graph classes with applications
• Map graphs
• Minimal scrambling sets of simple orders
• Minors and dimension
• New bounds on the edge number of ak-map graph
• Nowhere dense graph classes and dimension
• On a Coloring Problem.
• On the dimension of posets with cover graphs of treewidth 2
• On the dimensions of ordered sets of bounded degree
• On the order dimension of 1-sets versus \(k\)-sets
• Parameters tied to treewidth
• Planar Posets Have Dimension at Most Linear in Their Height
• Sparsity and dimension
• Structure of graphs with locally restricted crossings
• Suitable permutations, binary covering arrays, and Paley matrices
• The dimension of random ordered sets
• Topological minors of cover graphs and dimension
• Track layouts, layered path decompositions, and leveled planarity
• Tree-width and dimension

Cited in

(23)

• The Hardness of Approximating Poset Dimension
• Local boxicity
• Boxicity and maximum degree
• The graph of critical pairs of a crown
• The micro-world of cographs
• A note on lower bounds for boxicity of graphs
• Fractional local dimension
• On the boxicity of Kneser graphs and complements of line graphs
• Intersection dimension and graph invariants
• Separation dimension and degree
• Lower bounds for boxicity
• Boxicity, poset dimension, and excluded minors
• Poset boxicity of graphs
• Random bipartite posets and extremal problems
• The order dimension of divisibility
• Adjacency posets of outerplanar graphs
• Separating layered treewidth and row treewidth
• Clustered 3-colouring graphs of bounded degree
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• Local boxicity and maximum degree
• A fixed-parameter algorithm for dominance drawings of DAGs
• Word-representable graphs: orientations, posets, and bounds
• The dimension of divisibility orders and multiset posets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217895)