Boxicity and topological invariants

DOI10.1016/J.EJC.2015.07.020zbMATH Open1321.05283arXiv1503.05765OpenAlexW1869975288MaRDI QIDQ499501FDOQ499501

Authors: L. Esperet 

Publication date: 30 September 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The boxicity of a graph $G=(V,E)$ is the smallest integer $k$ for which there exist $k$ interval graphs $G_i=(V,E_i)$, $1leilek$, such that $E=E_{1}capcdotscap{E}_k$. In the first part of this note, we prove that every graph on $m$ edges has boxicity $O(sqrtmlogm)$, which is asymptotically best possible. We use this result to study the connection between the boxicity of graphs and their Colin de Verdi`ere invariant, which share many similarities. Known results concerning the two parameters suggest that for any graph $G$, the boxicity of $G$ is at most the Colin de Verdi`ere invariant of $G$, denoted by $mu(G)$. We observe that every graph $G$ has boxicity $O(mu(G{)}^4(logmu(G){)}^2)$, while there are graphs $G$ with boxicity $Omega(mu(G)sqrtlogmu(G))$. In the second part of this note, we focus on graphs embeddable on a surface of Euler genus $g$. We prove that these graphs have boxicity $O(sqrtglogg)$, while some of these graphs have boxicity $Omega(sqrtglogg)$. This improves the previously best known upper and lower bounds. These results directly imply a nearly optimal bound on the dimension of the adjacency poset of graphs on surfaces.

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

Recommendations

• Boxicity of graphs on surfaces
• Boxicity, poset dimension, and excluded minors
• Boxicity of Halin graphs
• Boxicity and maximum degree
• Local boxicity

zbMATH Keywords

Colin de Verdière invariant

Mathematics Subject Classification ID

Graph theory (05C99)

Cites Work

• Graphs on surfaces
• Interval representations of planar graphs
• Boxicity and treewidth
• Title not available (Why is that?)
• Dimension, graph and hypergraph coloring
• Boxicity of graphs on surfaces
• The dimension of random ordered sets
• Adjacency posets of planar graphs
• The Colin de Verdière number and sphere representations of a graph
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• From the plane to higher surfaces
• Multiplicity of the second Schrödinger eigenvalue on closed surfaces
• On the relation between two minor-monotone graph parameters
• Cubicity, degeneracy, and crossing number
• On the Colin de Verdière number of graphs

Cited In (12)

• The micro-world of cographs
• Boxicity of Halin graphs
• A note on lower bounds for boxicity of graphs
• On the box dimension of an invariant set
• Local boxicity
• Bounds for the boxicity of Mycielski graphs
• Local boxicity and maximum degree
• Local and union boxicity
• Boxicity of graphs on surfaces
• Better bounds for poset dimension and boxicity
• Boxicity, poset dimension, and excluded minors
• Box representations of embedded graphs

This page was built for publication: Boxicity and topological invariants

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