scientific article; zbMATH DE number 7272507

MaRDI QIDQ5133652zbMATH OpenFDO

Authors Gila Morgenstern, Martin Charles Golumbic

Publication date 10 November 2020

zbMATH Keywords

\(k\)-bend EPG graphbend numberedge intersection graphEPG graphgridHelly number

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• The complexity of Helly-B₁ EPG graph recognition
• Edge-intersection graphs of grid paths: the bend-number
• Edge intersection graphs of single bend paths on a grid
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• On split \(B_1\)-EPG graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• Computing maximum cliques in \(B_2\)-EPG graphs
• On edge-intersection graphs of k-bend paths in grids

Cited in

(24)

• On grid intersection graphs
• Edge-intersection graphs of boundary-generated paths in a grid
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• On split \(B_1\)-EPG graphs
• On edge intersection graphs of paths with 2 bends
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• Vertex Intersection Graphs of Paths on a Grid
• On edge intersection graphs of paths with 2 bends
• VPG and EPG bend-numbers of Halin graphs
• The complexity of Helly-B₁ EPG graph recognition
• On edge-intersection graphs of k-bend paths in grids
• scientific article; zbMATH DE number 1445371 (Why is no real title available?)
• 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
• A note on Helly-\(B_1\)-EPG graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• Helly and strong Helly numbers of B_k-EPG and B_k-VPG graphs
• Characterizations of cographs as intersection graphs of paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends

This page was built for publication:

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