Boxicity of Series Parallel graphs
Ankur Bohra, L. Sunil Chandran, J. Krishnam Raju
IISc-CSA-TR-2005-12
(September 2005) Available formats: [ps] [ps.gz]
Filed on September 21, 2005
Updated on September 21, 2005
The three well-known graph classes, planar graphs(${\cal P}$), series-parallel graphs (${\cal SP}$) and outer
planar graphs(${\cal OP}$) satisfy the following proper inclusion relation: ${\cal OP} \subset {\cal SP} \subset {\cal P}$.
It is known that $\mbox{box}(G) \le 3$ if $G \in {\cal P}$ and $\mbox{box}(G) \le 2$
if
$G \in {\cal 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 \cite{sunns2} showed that for any $G$,
$\mbox{box}(G) \le \mbox{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. \\
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2005/12/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]