Boxicity of Series Parallel Graphs
| dc.creator | Bohra, Ankur | |
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Raju, J. Krishnam | |
| dc.date | 2005-09-24 | |
| dc.date.accessioned | 2026-07-07T06:19:09Z | |
| dc.date.available | 2026-07-07T06:19:09Z | |
| dc.description | 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. | |
| dc.description | 10 pages, 0 figures | |
| dc.identifier | https://arxiv.org/abs/math/0509581 | |
| dc.identifier | http://arxiv.org/abs/math/0509581 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94981 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C62 | |
| dc.title | Boxicity of Series Parallel Graphs | |
| dc.type | text |