Vertex Intersection Graphs of Paths on a Grid

DOI10.7155/jgaa.00253zbMath1254.68184OpenAlexW4244914128MaRDI QIDQ3143733

Vincent Limouzy, Marina Lipshteyn, Elad Cohen, Michal Stern, Martin Charles Golumbic, Andrei Asinowski

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

zbMATH Keywords

string graphsgrid intersection graphschip manufacturing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (34)

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 ⋮ On approximating MIS over B1-VPG graphs* ⋮ On dominating set of some subclasses of string graphs ⋮ VPG and EPG bend-numbers of Halin graphs ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ Max point-tolerance graphs ⋮ Vertex intersection graphs of paths on a grid: characterization within block graphs ⋮ Vertex Contact Graphs of Paths on a Grid ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs ⋮ Good spanning trees in graph drawing ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ Characterization of 2-path signed network ⋮ On contact graphs of paths on a grid ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Posets and VPG graphs ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ 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 rectangle intersection graphs with stab number at most two ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ String graphs of k-bend paths on a grid ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ The maximum clique problem in multiple interval graphs

This page was built for publication: Vertex Intersection Graphs of Paths on a Grid