Boxicity of graphs on surfaces

Details Boxicity of graphs on surfaces Boxicity of graphs on surfaces

2011-07-11

arxiv.org/abs/1107.1953v2

Mathematics

Combinatorics

9 pages, 2 figures

Scientific paper

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)$, $1 \le i \le k$, such that $E=E_1 \cap ... \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.

Affiliated with

Also associated with

No associations

Rating

Boxicity of graphs on surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boxicity of graphs on surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity of graphs on surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137416