Edge-intersection graphs of grid paths: the bend-number
From MaRDI portal
Publication:2440108
DOI10.1016/j.dam.2013.10.035zbMath1284.05180arXiv1009.2861MaRDI 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
EPG-representations with Small Grid-Size, 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, Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid, Intersection graphs of L-shapes and segments in the plane, Graphs of edge-intersecting and non-splitting paths, Edge intersection graphs of \(L\)-shaped paths in grids, VPG and EPG bend-numbers of Halin graphs, On the bend-number of planar and outerplanar graphs, Clique coloring \(B_1\)-EPG graphs, Some properties of edge intersection graphs of single-bend paths on a grid, Characterizations of cographs as intersection graphs of paths on a grid, CPG graphs: some structural and hardness results, Three ways to cover a graph, Edge-intersection graphs of boundary-generated paths in a grid, On independent set in \(B_1\)-EPG graphs, Hardness and approximation for L-EPG and \(B_1\)-EPG graphs, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, On edge intersection graphs of paths with 2 bends, Proper circular arc graphs as intersection graphs of paths on a grid, On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid, On Edge Intersection Graphs of Paths with 2 Bends, Unnamed Item
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item