Better bounds for poset dimension and boxicity

DOI10.1090/TRAN/7962zbMATH Open1433.05233arXiv1804.03271OpenAlexW3103128284WikidataQ127205713 ScholiaQ127205713MaRDI QIDQ5217895FDOQ5217895

Authors: David R. Wood, Alex Scott 

Publication date: 26 February 2020

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (24)

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

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)