On k-Bend and Monotonic \ell-Bend Edge Intersection Graphs of Paths on a Grid

DOI10.1016/J.DAM.2023.01.010arXiv2002.05998MaRDI QIDQ6334802FDOQ6334802

Publication date: 14 February 2020

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_{e} l l^{m}

is the class of all graphs that have a monotonic

e l l

-bend EPG representation, i.e. an

e l l

-bend EPG representation, where each path is ascending in both columns and rows. It is trivial that

B_{k}^{m} s u b s e t e q B_{k}

for all

k

. Moreover, it is known that

B_{k}^{m} s u b s e t n e q q 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 i n 2, 3, 5

and for

k g e q s l a n t 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} s u b s e t n e q q B_{k}

holds also for

k i n 4, 6

. Furthermore, we show that

B_{k} o t s u b s e t e q B_{2 k - 9}^{m}

holds for all

k g e q s l a n t 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} s u b s e t e q B_{3}^{m}

holds, providing the first result of this kind.

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: On $k$-Bend and Monotonic $\ell$-Bend Edge Intersection Graphs of Paths on a Grid

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