Edge-intersection graphs of grid paths: the bend-number
Authors:
- Daniel HeldtDHDaniel Heldt
- Kolja KnauerKKKolja Knauer
- Torsten UeckerdtTUTorsten Ueckerdt
Preprint
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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- On the Bend-Number of Planar and Outerplanar GraphsLecture Notes in Computer Science, 2012
- Edge intersection graphs of systems of paths on a grid with a bounded number of bendsDiscrete Applied Mathematics, 2009
- Edge-Intersection Graphs of k-Bend Paths in Grids2009
- Caterpillar arboricity of planar graphsDiscrete Mathematics, 2007
- Partitioning Graphs of Bounded Tree-WidthCombinatorica, 1998
- Star arboricity of graphsDiscrete Mathematics, 1996
- Recognizing graphs with fixed interval number is NP-completeDiscrete Applied Mathematics, 1984
- The interval number of a planar graph: Three intervals sufficeJournal of Combinatorial Theory, Series B, 1983
- A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theoryNetworks, 1982
- On double and multiple interval graphsJournal of Graph Theory, 1979