2010/09/15 by Daniel Heldt, Heldt, Daniel, Kolja Knauer +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C62
paper · pdf · doi:10.48550/arxiv.1009.2861
33 pages, 20 figures
arxiv created 2012/08/20 · arxiv updated 2012/08/21
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 Km,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.