Edge intersection graphs of single bend paths on a grid

DOI10.1002/NET.20305MaRDI QIDQ3057113zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

intersection graphspath bendpaths on a grid

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 7272507
• Some properties of edge intersection graphs of single-bend paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Edge-intersection graphs of boundary-generated paths in a grid

Cites work

• Edge and vertex intersection of paths in a tree
• scientific article; zbMATH DE number 5763164 (Why is no real title available?)
• scientific article; zbMATH DE number 4185548 (Why is no real title available?)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Representing edge intersection graphs of paths on degree 4 trees
• Single bend wiring
• The edge intersection graphs of paths in a tree

Cited in

(46)

• Edge-intersection graphs of boundary-generated paths in a grid
• On superperfection of edge intersection graphs of paths
• 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
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Proper circular arc graphs as intersection graphs of paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• Improved algorithms for scheduling unsplittable flows on paths
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Intersection graphs of L-shapes and segments in the plane
• 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
• Some properties of edge intersection graphs of single bend paths on a grid
• Graphs of edge-intersecting and non-splitting paths
• Edge intersection graphs of \(L\)-shaped paths in grids
• Vertex Intersection Graphs of Paths on a Grid
• 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
• The complexity of Helly-B₁ EPG graph recognition
• Helly numbers of polyominoes
• Graphs of edge-intersecting and non-splitting one bend paths in a grid
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Clique coloring \(B_1\)-EPG graphs
• scientific article; zbMATH DE number 7272507 (Why is no real title available?)
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• On the bend number of circular-arc graphs as edge 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
• A note on Helly-\(B_1\)-EPG graphs
• A survey on variant domination problems in geometric intersection graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• On non-superperfection of edge intersection graphs of paths
• Characterizations and clique coloring of edge intersection graphs on a triangular grid
• Parameterized complexity of path set packing
• Helly and strong Helly numbers of B_k-EPG and B_k-VPG graphs
• Relationship among B₁-EPG, VPT and EPT graphs classes
• Clique cover on L-EPG representations of graphs
• Total (restrained) domination in B_k-EPG graphs and B_k-VPG graphs
• Characterizations of cographs as intersection graphs of paths on a grid
• CPG graphs: some structural and hardness results
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends

This page was built for publication: Edge intersection graphs of single bend paths on a grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057113)