VPG and EPG bend-numbers of Halin graphs

详细信息    查看全文

• 作者：Mathew C. Francis^a ; ^{mathew@isichennai.res.in" class="auth_mail" title="E-mail the corresponding author} ; Abhiruk Lahiri^b ; ^{abhiruk.lahiri@csa.iisc.ernet.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：VPG graph ; EPG graph ; Halin graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：95-105
• 全文大小：500 K

文摘

A piecewise linear simple curve in the plane made up of k+1$k+1$ line segments, each of which is either horizontal or vertical, with consecutive segments being of different orientation is called a 82d69cac4ec4867925f82ed55b15bf" title="Click to view the MathML source">k$k$-bend path  . Given a graph G$G$, a collection of 82d69cac4ec4867925f82ed55b15bf" title="Click to view the MathML source">k$k$-bend paths in which each path corresponds to a vertex in G$G$ and two paths have a common point if and only if the vertices corresponding to them are adjacent in G$G$ is called a B_k$B_k$-VPG representation   of G$G$. Similarly, a collection of 82d69cac4ec4867925f82ed55b15bf" title="Click to view the MathML source">k$k$-bend paths each of which corresponds to a vertex in G$G$ is called an B_k$B_k$-EPG representation   of G$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$G$. The VPG bend-number  b_v(G)$b_v\left(G\right)$ of a graph G$G$ is the minimum 82d69cac4ec4867925f82ed55b15bf" title="Click to view the MathML source">k$k$ such that G$G$ has a B_k$B_k$-VPG representation. Similarly, the EPG bend-number  b_e(G)$b_e\left(G\right)$ of a graph G$G$ is the minimum 82d69cac4ec4867925f82ed55b15bf" title="Click to view the MathML source">k$k$ such that G$G$ has a B_k$B_k$-EPG representation. Halin graphs   are the graphs formed by taking a tree with no degree 2$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$G$ is a Halin graph then d05" title="Click to view the MathML source">b_v(G)≤1$b_v\left(G\right)\le 1$ and b_e(G)≤2$b_e\left(G\right)\le 2$. These bounds are tight. In fact, we prove the stronger result that if G$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.