Edge intersection graphs of single bend paths on a grid
From MaRDI portal
Publication:3057113
DOI10.1002/net.20305zbMath1208.05090OpenAlexW2403103020MaRDI QIDQ3057113
Marina Lipshteyn, Michal Stern, Martin Charles Golumbic
Publication date: 24 November 2010
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.20305
Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
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 the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, On Edge Intersection Graphs of Paths with 2 Bends, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, VPG and EPG bend-numbers of Halin graphs, Edge-Intersection Graphs of k-Bend Paths in Grids, Helly numbers of polyominoes, 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, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Parameterized complexity of path set packing, Edge-intersection graphs of boundary-generated paths in a grid, Improved algorithms for scheduling unsplittable flows on paths, On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid, Edge-intersection graphs of grid paths: the bend-number, Unnamed Item, On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, 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, Edge intersection graphs of systems of paths on a grid with a bounded number of bends, Characterizations of cographs as intersection graphs of paths on 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”, On superperfection of edge intersection graphs of paths, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, Some properties of edge intersection graphs of single bend paths on a grid
Cites Work
