Boxicity of series-parallel graphs

DOI10.1016/J.DISC.2006.04.014MaRDI QIDQ2509298zbMATH OpenOpenAlexFDO

Authors Ankur Bohra, L. Sunil Chandran, J. Krishnam Raju

Publication date 19 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509581

zbMATH Keywords

boxicityseries-parallel graphs\(k\)-tress

Mathematics Subject Classification ID

Graph theory (05C99)

Abstract: 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.

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Interval representations of planar graphs

Cited in

(11)

• Boxicity of Halin graphs
• scientific article; zbMATH DE number 844157 (Why is no real title available?)
• Boxicity of leaf powers
• scientific article; zbMATH DE number 5214885 (Why is no real title available?)
• Separation dimension of graphs and hypergraphs
• A characterization of box-bounded degree sequences of graphs
• An upper bound for cubicity in terms of boxicity
• scientific article; zbMATH DE number 6254006 (Why is no real title available?)
• Trader multiflow and box-TDI systems in series-parallel graphs
• SOME PROPERTIES OF BINARY SERIES-PARALLEL GRAPHS
• Representing graphs as the intersection of cographs and threshold graphs

This page was built for publication: Boxicity of series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509298)