Search

Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if is a Halin graph that is not isomorphic to , then . In fact, we prove the stronger result that if is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless is isomorphic to (in which case its boxicity is 1). [Copyright &y& Elsevier]