VPG and EPG bend-numbers of Halin graphs

A piecewise linear simple curve in the plane made up of k + 1 line segments, each of which is either horizontal or vertical, with consecutive segments being of different orientation is called a k -bend path. Given a graph G, a collection of k -bend paths in which each path corresponds to a vertex in G and two paths have a common point if and only if the vertices corresponding to them are adjacent in G is called a B k -VPG representation of G . Similarly, a collection of k -bend paths each of which corresponds to a vertex in G is called an B k -EPG representation of G if any two paths have a line segment of non-zero length in common if and only if their corresponding vertices are adjacent in G . The VPG bend-number b v ( G ) of a graph G is the minimum k such that G has a B k -VPG representation. Similarly, the EPG bend-number b e ( G ) of a graph G is the minimum k such that G has a B k -EPG representation. 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 G is a Halin graph then b v ( G ) ź 1 and b e ( G ) ź 2 . These bounds are tight. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree to form a simple cycle, then it has a VPG-representation using only one type of 1-bend paths and an EPG-representation using only one type of 2-bend paths.