Edge-intersection graphs of grid paths: the bend-number

DOI10.1016/J.DAM.2013.10.035MaRDI QIDQ2440108zbMATH OpenOpenAlexFDO

Authors Daniel Heldt, Kolja Knauer, Torsten Ueckerdt

Publication date 27 March 2014

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

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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We investigate edge-intersection graphs of paths in the plane grid, regarding a parameter called the bend-number. I.e., every vertex is represented by a grid path and two vertices are adjacent if and only if the two grid paths share at least one grid-edge. The bend-number is the minimum

k

such that grid-paths with at most

k

bends each suffice to represent a given graph. This parameter is related to the interval-number and the track-number of a graph. We show that for every

k

there is a graph with bend-number

k

. Moreover we provide new upper and lower bounds of the bend-number of graphs in terms of degeneracy, treewidth, edge clique covers and the maximum degree. Furthermore we give bounds on the bend-number of

K_{m, n}

and determine it exactly for some pairs of

m

and

n

. Finally, we prove that recognizing single-bend graphs is NP-complete, providing the first such result in this field.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Edge-intersection graphs of grid paths: the bend-number

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