Splitting B₂-VPG graphs into outer-string and co-comparability graphs

2016/12/21 by Martin Derka, Derka, Martin, Thérèse Biedl +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1612.07276

openalex publication_date 2016/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we show that any B₂-VPG graph (i.e., an intersection graph of orthogonal curves with at most 2 bends) can be decomposed into O(log n) outerstring graphs or O(log³ n) permutation graphs. This leads to better approximation algorithms for hereditary graph problems, such as independent set, clique and clique cover, on B₂-VPG graphs.

Citations

• Approximation algorithms for NP-complete problems on planar graphs

Related

• Characterization and a 2D Visualization of B₀-VPG Cocomparability\n Graphs
• Approximating Independent Set and Dominating Set on VPG graphs
• Approximation Algorithms for Independence and Domination on B₁-VPG and B₁-EPG Graphs
• Computing maximum cliques in B₂-EPG graphs
• A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid