2 papers
math.CO2005
Boxicity of Series Parallel Graphs
Ankur Bohra, L. Sunil Chandran, J. Krishnam Raju
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 kn…
math.CO2005
Boxicity and Treewidth
L. Sunil Chandran, Naveen Sivadasan
In this paper, we relate the seemingly unrelated concepts of treewidth and boxicity. Our main result is that, for any graph G, boxicity(G) <= treewidth(G) + 2. We also show that th…