Hardness and approximation for L-EPG and B₁-EPG graphs

DOI10.1016/J.DAM.2019.10.004zbMATH Open1440.05154OpenAlexW2982485164MaRDI QIDQ2184686FDOQ2184686

Authors: Dror Epstein, Martin Charles Golumbic, Abhiruk Lahiri, Gila Morgenstern 

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.10.004

Recommendations

• Approximation algorithms for \(B _{1}\)-EPG graphs
• On independent set in \(B_1\)-EPG graphs
• On independent set on B1-EPG graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• On edge intersection graphs of paths with 2 bends

zbMATH Keywords

paths on a gridedge intersection graphB1-EPG graphs\(k\)-simplicial graphsfully-subdivided graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• The Complexity of Coloring Circular Arcs and Chords
• Edge-intersection graphs of grid paths: the bend-number
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• On edge-intersection graphs of \(k\)-bend paths in grids
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• Scheduling Split Intervals
• VPG and EPG bend-numbers of Halin graphs
• On the bend-number of planar and outerplanar graphs
• Optimization problems in multiple-interval graphs
• Title not available (Why is that?)
• Approximation algorithms for intersection graphs
• 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 boundary-generated paths in a grid
• Title not available (Why is that?)
• Characterizations of cographs as intersection graphs of paths on a grid
• On edge intersection graphs of paths with 2 bends
• Proper circular arc graphs as intersection graphs of paths on a grid
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• 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
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• On independent set on B1-EPG graphs
• On split \(B_1\)-EPG graphs
• The complexity of Helly-\(B_1\) EPG graph recognition

Cited In (9)

• Edge intersection graphs of \(L\)-shaped paths in grids
• Approximating domination on intersection graphs of paths on a grid
• Maximum independent set on \(B_1\)-VPG graphs
• On independent set on B1-EPG graphs
• Approximation algorithms for \(B _{1}\)-EPG graphs
• On independent set in \(B_1\)-EPG graphs
• Computing maximum cliques in \(B_2\)-EPG graphs
• Title not available (Why is that?)
• On split \(B_1\)-EPG graphs

This page was built for publication: Hardness and approximation for L-EPG and \(B_1\)-EPG graphs

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