Dushnik-Miller dimension of contact systems of d -dimensional boxes

Mathew Francis Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Planar graphs are the graphs with Dushnik-Miller dimension at most three (W. Schnyder, Planar graphs and poset dimension, Order 5, 323-343, 1989). Consider the intersection graph of interior disjoint axis-parallel rectangles in the plane. It is known that if at most three rectangles intersect on a point, then this intersection graph is planar, that is it has Dushnik-Miller dimension at most three. This paper aims at generalizing this from the plane to by considering tilings of with axis parallel boxes, where at most boxes intersect on a point. Such tilings induce simplicial complexes and we will show that those simplicial complexes have Dushnik-Miller dimension at most.
Type de document :
Article dans une revue
Electronic Notes in Discrete Mathematics, Elsevier, 2017, 61, pp.467-473. 〈10.1016/j.endm.2017.06.075〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01693192
Contributeur : Isabelle Gouat <>
Soumis le : jeudi 25 janvier 2018 - 21:43:27
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

Citation

Mathew Francis, Daniel Gonçalves. Dushnik-Miller dimension of contact systems of d -dimensional boxes. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 61, pp.467-473. 〈10.1016/j.endm.2017.06.075〉. 〈lirmm-01693192〉

Partager

Métriques

Consultations de la notice

121