Approximation algorithms for NP-complete problems on planar graphs

1994/01/02 by Brenda S. Baker · 48 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Advanced Graph Theory Research

paper · pdf · doi:10.1145/174644.174650

Abstract

This paper describes a general technique that can be used to obtain approximation schemes for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k-outerplanar.

Citations

• Efficient Planarity Testing

Cited by

• Beyond Degree Four: Near-Orthogonal Planar Drawings
• Complexity of Eliminating (Majority) Illusion in Directed Networks
• Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
• Non-aligned drawings of planar graphs
• A Variant of the Maximum Weight Independent Set Problem
• Tree t-spanners in Outerplanar Graphs via Supply Demand Partition
• Approximation Schemes for Planar Graph Connectivity Problems
• TCP Reno over Adaptive CSMA
• On the Induced Matching Problem in Hamiltonian Bipartite Graphs
• Minimum k-way cut of bounded size is fixed-parameter tractable
• The two-edge connectivity survivable-network design problem in planar\n graphs
• Geometry based heuristics for unit disk graphs
• Minimum Vertex Cover in Rectangle Graphs
• Dynamic Meta-Kernelization
• PACE Solver Description: twin_width_fmi
• Wireless Network Scheduling with Discrete Propagation Delays: Theorems and Algorithms
• Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
• Results on independent sets in categorical products of graphs, the ultimate categorical independence ratio and the ultimate categorical independent domination ratio
• A fixed-parameter algorithm for the minimum Manhattan network problem
• An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure
• Capacitated Dominating Set on Planar Graphs
• Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite\n graphs
• PTAS for k-tour cover problem on the plane for moderately large values of k
• Domination in graphs with bounded propagation: algorithms, formulations and hardness results
• Joint Scheduling and Multiflow Maximization in Wireless Networks
• Deciding first-order properties of locally tree-decomposable structures
• The Price of Connectivity Augmentation on Planar Graphs
• On independent set on B1-EPG graphs
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
• Clan Embeddings into Trees, and Low Treewidth Graphs
• Kernelization and approximation of distance-r independent sets on\n nowhere dense graphs
• Induced Minors, Asymptotic Dimension, and Baker's Technique
• Optimal Coalition Structures in Cooperative Graph Games
• An n^{O(loglog n)} time approximation scheme for capacitated VRP in the Euclidean plane
• Dynamic Generators of Topologically Embedded Graphs
• Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
• Welfare optimization for resource allocation with peer effects
• Parameter testing with bounded degree graphs of subexponential growth
• On triangulating k-outerplanar graphs
• Constant-factor approximation of domination number in sparse graphs
• Splitting B₂-VPG graphs into outer-string and co-comparability graphs
• Computing bounded-width tree and branch decompositions of k-outerplanar\n graphs
• Prize-collecting Network Design on Planar Graphs
• The Complexity of Maximum k-Order Bounded Component Set Problem
• A local constant factor approximation for the minimum dominating set problem on bounded genus graphs
• On the treewidths of graphs of bounded degree. [europepmc]
• New Tools and Connections for Exponential-Time Approximation. [europepmc]
• (Re)packing Equal Disks into Rectangle. [europepmc]

Related

• Thin graph classes and polynomial-time approximation schemes
• Strengthening Hardness Results to 3-Connected Planar Graphs
• An Improved Algorithm for Finding Maximum Outerplanar Subgraphs
• Plane Decompositions as Tools for Approximation
• Polylogarithmic approximation for minimum planarization (almost)