On edge intersection graphs of paths with 2 bends
From MaRDI portal
Publication:2357780
DOI10.1016/j.dam.2017.04.023zbMath1365.05209arXiv1711.05096WikidataQ62595898 ScholiaQ62595898MaRDI QIDQ2357780
Martin Pergel, Paweł Rzążewski
Publication date: 14 June 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.05096
05C38: Paths and cycles
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
CPG graphs: some structural and hardness results, Edge-intersection graphs of boundary-generated paths in a grid, Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Edge intersection graphs of \(L\)-shaped paths in grids
- On the bend-number of planar and outerplanar graphs
- Some properties of edge intersection graphs of single-bend paths on a grid
- Edge intersection graphs of systems of paths on a grid with a bounded number of bends
- Unit disk graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The maximum clique problem in multiple interval graphs
- Edge-intersection graphs of grid paths: the bend-number
- Approximation Algorithms for B 1-EPG Graphs
- Edge intersection graphs of single bend paths on a grid
- On Edge Intersection Graphs of Paths with 2 Bends
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Scheduling Split Intervals