Boxicity, Poset Dimension, and Excluded Minors

2018/12/21 by Louis Esperet, Veit Wiechert · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Partially ordered set #Intersection (aeronautics) #Graph #Intersection graph #Dimension (graph theory) #Interval graph #Discrete mathematics #Interval (graph theory) #Chordal graph #Line graph #1-planar graph

paper · pdf · doi:10.37236/7787

published in The Electronic Journal of Combinatorics 25(4) (Electronic Journal of Combinatorics)

openalex publication_date 2018/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02

Abstract

In this short note, we relate the boxicity of graphs (and the dimension of posets) with their generalized coloring parameters. In particular, together with known estimates, our results imply that any graph with no K_t-minor can be represented as the intersection of O(t²log t) interval graphs (improving the previous bound of O(t⁴)), and as the intersection of \tfrac152 t² circular-arc graphs.

Citations

• Boxicity and Poset Dimension
• Interval representations of planar graphs
• Lower bound of the hadwiger number of graphs by their average degree
• An extremal function for contractions of graphs

Cited by

• Boxicity [wikipedia]