Vertex Intersection Graphs of Paths on a Grid
DOI10.7155/JGAA.00253zbMATH Open1254.68184OpenAlexW4244914128MaRDI QIDQ3143733FDOQ3143733
Authors: Elad Cohen, Vincent Limouzy, Marina Lipshteyn, Michal Stern, Andrei Asinowski, Martin Charles Golumbic 
Publication date: 4 December 2012
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00253
Recommendations
- scientific article; zbMATH DE number 7272507
- On grid intersection graphs
- Vertex intersection graphs of paths on a grid: characterization within block graphs
- Vertex contact graphs of paths on a grid
- Edge-intersection graphs of boundary-generated paths in a grid
- Edge and vertex intersection of paths in a graph
- Vertex contact representations of paths on a grid
- Edge intersection graphs of \(L\)-shaped paths in grids
- Edge intersection graphs of single bend paths on a grid
- Characterizations of cographs as intersection graphs of paths on a grid
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Network design and communication in computer systems (68M10)
Cited In (39)
- Bounds on the bend number of split and cocomparability graphs
- CPG graphs: some structural and hardness results
- Vertex contact graphs of paths on a grid
- String graphs of \(k\)-bend 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
- Characterization of 2-path signed network
- Intersection graphs of L-shapes and segments in the plane
- Planar graphs as VPG-graphs
- On contact graphs of paths on a grid
- Posets and VPG graphs
- On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
- Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
- Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
- On dominating set of some subclasses of string graphs
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Vertex intersection graphs of paths on a grid: characterization within block graphs
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Maximum independent set on \(B_1\)-VPG graphs
- Characterizations of cographs as intersection graphs of paths on a grid
- On rectangle intersection graphs with stab number at most two
- VPG and EPG bend-numbers of Halin graphs
- B0-VPG Representation of AT-free Outerplanar Graphs
- Recognizing geometric intersection graphs stabbed by a line
- Max point-tolerance graphs
- The maximum clique problem in multiple interval graphs
- On some special classes of contact \(B_0\)-VPG graphs
- Planar graphs as VPG-graphs
- On approximating MIS over B1-VPG graphs*
- \(B_0\)-VPG representation of AT-free outerplanar graphs
- Approximating dominating set on intersection graphs of rectangles and L-frames
- Characterising circular-arc contact \(B_0\)-VPG graphs
- On grid intersection graphs
- Vertex contact representations of paths on a grid
- A survey on variant domination problems in geometric intersection graphs
- Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
- A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
- Good spanning trees in graph drawing
- Computing maximum independent set on outerstring graphs and their relatives
This page was built for publication: Vertex Intersection Graphs of Paths on a Grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143733)
