Edge-intersection graphs of grid paths: the bend-number
From MaRDI portal
Publication:2440108
DOI10.1016/j.dam.2013.10.035zbMath1284.05180arXiv1009.2861OpenAlexW1989478743MaRDI QIDQ2440108
Kolja Knauer, Torsten Ueckerdt, Daniel Heldt
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)
Related Items (23)
On edge intersection graphs of paths with 2 bends ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ Intersection graphs of L-shapes and segments in the plane ⋮ CPG graphs: some structural and hardness results ⋮ Graphs of edge-intersecting and non-splitting paths ⋮ Edge intersection graphs of \(L\)-shaped paths in grids ⋮ On Edge Intersection Graphs of Paths with 2 Bends ⋮ VPG and EPG bend-numbers of Halin graphs ⋮ On independent set in \(B_1\)-EPG graphs ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ Three ways to cover a graph ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ Unnamed Item ⋮ EPG-representations with Small Grid-Size ⋮ Some properties of edge intersection graphs of single-bend paths on a grid ⋮ On the bend-number of planar and outerplanar graphs ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Clique coloring \(B_1\)-EPG graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Recognizing graphs with fixed interval number is NP-complete
- The interval number of a planar graph: Three intervals suffice
- Three ways to cover a graph
- Edge intersection graphs of systems of paths on a grid with a bounded number of bends
- On star and caterpillar arboricity
- Star arboricity
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Partitioning graphs of bounded tree-width
- Star arboricity of graphs
- Caterpillar arboricity of planar graphs
- Representing edge intersection graphs of paths on degree 4 trees
- Approximation Algorithms for B 1-EPG Graphs
- Some properties of edge intersection graphs of single bend paths on a grid
- Edge intersection graphs of single bend paths on a grid
- On double and multiple interval graphs
- Recognizing d-Interval Graphs and d-Track Interval Graphs
- Some results on linear arboricity
- A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
- Extremal Values of the Interval Number of a Graph
- The complexity of satisfiability problems
- k-Degenerate Graphs
This page was built for publication: Edge-intersection graphs of grid paths: the bend-number
