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

DOI10.1016/J.DAM.2013.10.035zbMATH Open1284.05180arXiv1009.2861OpenAlexW1989478743MaRDI QIDQ2440108FDOQ2440108

Authors: Daniel Heldt, Kolja Knauer, Torsten Ueckerdt 

Publication date: 27 March 2014

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

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.

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

Recommendations

• On edge-intersection graphs of \(k\)-bend paths in grids
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends

zbMATH Keywords

intersection graphsgrid paths

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Representing edge intersection graphs of paths on degree 4 trees
• Title not available (Why is that?)
• The complexity of satisfiability problems
• k-Degenerate Graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• On edge-intersection graphs of \(k\)-bend paths in grids
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• Star arboricity
• Title not available (Why is that?)
• Star arboricity of graphs
• Title not available (Why is that?)
• On star and caterpillar arboricity
• Partitioning graphs of bounded tree-width
• Caterpillar arboricity of planar graphs
• On double and multiple interval graphs
• Some results on linear arboricity
• Title not available (Why is that?)
• Extremal Values of the Interval Number of a Graph
• Title not available (Why is that?)
• The interval number of a planar graph: Three intervals suffice
• Three ways to cover a graph
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Recognizing graphs with fixed interval number is NP-complete
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Some properties of edge intersection graphs of single bend paths on a grid

Cited In (33)

• CPG graphs: some structural and hardness results
• Edge-intersection graphs of boundary-generated paths in a grid
• Single bend paths on a grid have strong Helly number 4: errata atque emendationes ad ``Edge intersection graphs of single bend paths on a grid
• Proper circular arc graphs as intersection graphs of paths on a grid
• EPG-representations with Small Grid-Size
• Intersection graphs of L-shapes and segments in the plane
• Edge intersection graphs of \(L\)-shaped paths in grids
• Bend complexity and Hamiltonian cycles in grid graphs
• Graphs of edge-intersecting and non-splitting paths
• Posets and VPG graphs
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Some properties of edge intersection graphs of single bend paths on a grid
• On edge intersection graphs of paths with 2 bends
• Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
• Some properties of edge intersection graphs of single-bend paths on a grid
• On edge intersection graphs of paths with 2 bends
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Characterizations of cographs as intersection graphs of paths on a grid
• VPG and EPG bend-numbers of Halin graphs
• On the bend-number of planar and outerplanar graphs
• On edge-intersection graphs of \(k\)-bend paths in grids
• On independent set in \(B_1\)-EPG graphs
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Three ways to cover a graph
• The complexity of Helly-\(B_1\) EPG graph recognition
• Title not available (Why is that?)
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Edge intersection graphs of single bend paths on a grid
• Clique coloring \(B_1\)-EPG graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

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)