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

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

zbMATH Keywords

intersection graphs; grid paths

Mathematics Subject Classification ID

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