## Abstract

If a graph G can be represented by means of paths on a grid, such that each vertex of G corresponds to one path on the grid and two vertices of G are adjacent if and only if the corresponding paths share a grid edge, then this graph is called EPG and the representation is called EPG representation. A k-bend EPG representation is an EPG representation in which each path has at most k bends. The class of all graphs that have a k-bend EPG representation is denoted by B
_{k}. B
_{ℓ}
^{m} is the class of all graphs that have a monotonic ℓ-bend EPG representation, i.e. an ℓ-bend EPG representation, where each path is ascending in both columns and rows. It is trivial that B
_{k}
^{m}⊆B
_{k} for all k. Moreover, it is known that B
_{k}
^{m}⫋B
_{k}, for k=1. By investigating the B
_{k}-membership and the B
_{k}
^{m}-membership of complete bipartite graphs we prove that the inclusion is also proper for k∈{2,3,5} and for k⩾7. In particular, we derive necessary conditions for this membership that have to be fulfilled by m, n and k, where m and n are the number of vertices on the two partition classes of the bipartite graph. We conjecture that B
_{k}
^{m}⫋B
_{k} holds also for k∈{4,6}. Furthermore, we show that B
_{k}⁄⊆B
_{2k−9}
^{m} holds for all k⩾5. This implies that restricting the shape of the paths can lead to a significant increase of the number of bends needed in an EPG representation. So far no bounds on the amount of that increase were known. We prove that B
_{1}⊆B
_{3}
^{m} holds, providing the first result of this kind.

Original language | English |
---|---|

Pages (from-to) | 88-103 |

Number of pages | 16 |

Journal | Discrete Applied Mathematics |

Volume | 331 |

DOIs | |

Publication status | Published - 31 May 2023 |

## Keywords

- (Monotonic) bend number
- Complete bipartite graph
- EPG graph
- Paths on a grid

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fields of Expertise

- Information, Communication & Computing