# On k-bend and monotonic ℓ-bend edge intersection graphs of paths on a grid

Eranda Çela*, Elisabeth Gaar

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

## 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 88-103 16 Discrete Applied Mathematics 331 https://doi.org/10.1016/j.dam.2023.01.010 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

## Fingerprint

Dive into the research topics of 'On k-bend and monotonic ℓ-bend edge intersection graphs of paths on a grid'. Together they form a unique fingerprint.