On Comparable Box Dimension

DOI10.4230/LIPICS.SOCG.2022.38MaRDI QIDQ6393719zbMATH OpenFDO

Authors Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, Torsten Ueckerdt

Publication date 15 March 2022

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2022.38

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Two boxes in $mathbb{R}^d$ are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph $G$ is the minimum integer $d$ such that $G$ can be represented as a touching graph of comparable axis-aligned boxes in $mathbb{R}^d$. We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion.

Recommendations

• Boxicity, poset dimension, and excluded minors
• Boxicity and treewidth
• Boxicity and maximum degree

Cited in

(9)

• Grid minors and products
• Powers of planar graphs, product structure, and blocking partitions
• Product structure of graph classes with bounded treewidth
• Treewidth 2 in the planar graph product structure theorem
• Powers of planar graphs, product structure, and blocking partitions (extended abstract)
• Product structure of graph classes with bounded treewidth
• Product structure of graph classes with strongly sublinear separators
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• Intersection graphs with and without product structure

This page was built for publication: On Comparable Box Dimension

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