Boxicity of graphs on surfaces

DOI10.1007/S00373-012-1130-XzbMATH Open1267.05083arXiv1107.1953OpenAlexW3098458351MaRDI QIDQ2376090FDOQ2376090

Authors: L. Esperet, Gwenaël Joret 

Publication date: 26 June 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The boxicity of a graph $G=(V,E)$ is the least integer $k$ for which there exist $k$ interval graphs $G_i=(V,E_i)$, $1leilek$, such that $E=E_{1}cap\mathrm{...}cap{E}_k$. Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface $Sigma$ of genus $g$ is at most $5g+3$. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.

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

Recommendations

• Boxicity and topological invariants
• Box representations of embedded graphs
• Boxicity of Halin graphs
• An upper bound for cubicity in terms of boxicity
• Boxicity, poset dimension, and excluded minors

zbMATH Keywords

graphs on surfacesacyclic coloringboxicityminor-closed classes

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Cites Work

• Graphs on surfaces
• An extremal function for contractions of graphs
• Title not available (Why is that?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Coloring with no 2-colored \(P_4\)'s
• Title not available (Why is that?)
• Interval representations of planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and treewidth
• Title not available (Why is that?)
• Dimension, graph and hypergraph coloring
• On acyclic colorings of graphs on surfaces
• Minimal scrambling sets of simple orders
• Adjacency posets of planar graphs
• Star coloring and acyclic coloring of locally planar graphs
• Title not available (Why is that?)
• Graphs on the torus and geometry of numbers
• Boxicity and maximum degree
• Cubicity, degeneracy, and crossing number

Cited In (15)

• Boxicity of Halin graphs
• A note on lower bounds for boxicity of graphs
• Boxicity of circular arc graphs
• Poset boxicity of graphs
• A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\)
• Separation dimension of graphs and hypergraphs
• Adjacency posets of outerplanar graphs
• On the stab number of rectangle intersection graphs
• Local and union boxicity
• On the boxicity of Kneser graphs and complements of line graphs
• Boxicity and topological invariants
• Better bounds for poset dimension and boxicity
• Chronological rectangle digraphs which are two-terminal series-parallel
• Boxicity, poset dimension, and excluded minors
• Box representations of embedded graphs

This page was built for publication: Boxicity of graphs on surfaces

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