Boxicity of Series Parallel Graphs

Details Boxicity of Series Parallel Graphs Boxicity of Series Parallel Graphs

2005-09-24

arxiv.org/abs/math/0509581v1

Mathematics

Combinatorics

10 pages, 0 figures

Scientific paper

The three well-known graph classes, planar graphs (P), series-parallel graphs(SP) and outer planar graphs(OP) satisfy the following proper inclusion relation: OP C SP C P. It is known that box(G) <= 3 if G belongs to P and box(G) <= 2 if G belongs to OP. Thus it is interesting to decide whether the maximum possible value of the boxicity of series-parallel graphs is 2 or 3. In this paper we construct a series-parallel graph with boxicity 3, thus resolving this question. Recently Chandran and Sivadasan showed that for any G, box(G) <= treewidth(G)+2. They conjecture that for any k, there exists a k-tree with boxicity k+1. (This would show that their upper bound is tight but for an additive factor of 1, since the treewidth of any k-tree equals k.) The series-parallel graph we construct in this paper is a 2-tree with boxicity 3 and is thus a first step towards proving their conjecture.

Affiliated with

Also associated with

No associations

Rating

Boxicity of Series Parallel Graphs 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 Series Parallel Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity of Series Parallel Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553015