Box representations of embedded graphs

DOI10.1007/S00454-016-9837-8MaRDI QIDQ527439zbMATH OpenOpenAlexFDO

Authors L. Esperet

Publication date 11 May 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

boxicitylocally planar graphstoroidal graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A $d$-box is the cartesian product of $d$ intervals of $mathbbR$ and a $d$-box representation of a graph $G$ is a representation of $G$ as the intersection graph of a set of $d$-boxes in $mathbb{R}^d$. It was proved by Thomassen in 1986 that every planar graph has a 3-box representation. In this paper we prove that every graph embedded in a fixed orientable surface, without short non-contractible cycles, has a 5-box representation. This directly implies that there is a function $f$, such that in every graph of genus $g$, a set of at most $f(g)$ vertices can be removed so that the resulting graph has a 5-box representation. We show that such a function $f$ can be made linear in $g$. Finally, we prove that for any proper minor-closed class $mathcalF$, there is a constant $c(mathcalF)$ such that every graph of $mathcalF$ without cycles of length less than $c(mathcalF)$ has a 3-box representation, which is best possible.

Recommendations

• Boxicity of graphs on surfaces
• Interval representations of planar graphs
• Contact representations of planar graphs with cubes
• Boxicity and topological invariants
• Boxicity, poset dimension, and excluded minors

Cites work

• A note on circular chromatic number of graphs with large girth and similar problems
• Boxicity and topological invariants
• Boxicity of graphs on surfaces
• Disjoint paths, planarizing cycles, and spanning walks
• Five-coloring maps on surfaces
• From the plane to higher surfaces
• Graphs on surfaces
• Graphs on the torus and geometry of numbers
• High-girth graphs avoiding a minor are nearly bipartite
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Interval representations of planar graphs
• Lower bounds for boxicity
• Ramanujan graphs
• Star coloring and acyclic coloring of locally planar graphs

Cited in

(4)

• Interval representations of planar graphs
• Boxicity of graphs on surfaces
• Better bounds for poset dimension and boxicity
• A note on lower bounds for boxicity of graphs

This page was built for publication: Box representations of embedded graphs

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