CPG graphs: some structural and hardness results
From MaRDI portal
Publication:827595
DOI10.1016/j.dam.2020.11.018zbMath1457.05070arXiv1903.01805OpenAlexW3112097173MaRDI QIDQ827595
Andrea Munaro, Nicolas Champseix, Bernard Ries, Esther Galby
Publication date: 13 January 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.01805
Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Intersection graphs of L-shapes and segments in the plane
- VPG and EPG bend-numbers of Halin graphs
- On the bend-number of planar and outerplanar graphs
- Clique coloring \(B_1\)-EPG graphs
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs requiring exponential representations
- Unit disk graphs
- Some simplified NP-complete graph problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Classes and recognition of curve contact graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- On contact graphs of paths on a grid
- Face covers and the genus problem for apex graphs
- On edge intersection graphs of paths with 2 bends
- Bounded clique cover of some sparse graphs
- Boundary classes for graph problems involving non-local properties
- Vertex intersection graphs of paths on a grid: characterization within block graphs
- Edge-intersection graphs of grid paths: the bend-number
- Approximation Algorithms for B 1-EPG Graphs
- Planar Graphs as VPG-Graphs
- Equilateral L-Contact Graphs
- Edge intersection graphs of single bend paths on a grid
- Vertex Intersection Graphs of Paths on a Grid
- Vertex Contact Representations of Paths on a Grid
- The Complexity of Multiterminal Cuts
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Combinatorial and Geometric Properties of Planar Laman Graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Recognizing string graphs in NP
- Posets and VPG graphs
This page was built for publication: CPG graphs: some structural and hardness results
