VPG and EPG bend-numbers of Halin graphs

DOI10.1016/J.DAM.2016.07.007zbMATH Open1346.05135arXiv1505.06036OpenAlexW2237852414MaRDI QIDQ323044FDOQ323044

Authors: Mathew C. Francis, Abhiruk Lahiri 

Publication date: 7 October 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A piecewise linear 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)leq1$ and $b_e(G)leq2$. 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.

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

Recommendations

• Edge intersection graphs of single bend paths on a grid
• Planar graphs as VPG-graphs
• Planar graphs as VPG-graphs
• scientific article; zbMATH DE number 7272507
• Vertex Intersection Graphs of Paths on a Grid

zbMATH Keywords

Halin graphEPG graphVPG graph

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• Edge-intersection graphs of grid paths: the bend-number
• Equilateral L-contact graphs
• Edge intersection graphs of single bend paths on a grid
• Vertex Intersection Graphs of Paths on a Grid
• Title not available (Why is that?)
• String graphs of \(k\)-bend paths on a grid
• Vertex contact representations of paths on a grid
• On the bend-number of planar and outerplanar graphs
• 1-string \(B_2\)-VPG representation of planar graphs

Cited In (14)

• Bounds on the bend number of split and cocomparability graphs
• CPG graphs: some structural and hardness results
• Edge-intersection graphs of boundary-generated paths in a grid
• Order-preserving 1-string representations of planar graphs
• Proper circular arc graphs as intersection graphs of paths on a grid
• EPG-representations with Small Grid-Size
• On contact graphs of paths on a grid
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
• Listing all spanning trees in Halin graphs -- sequential and parallel view
• Drawing Halin-graphs with small height
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• Characterising circular-arc contact \(B_0\)-VPG graphs

This page was built for publication: VPG and EPG bend-numbers of Halin graphs

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