Approximation algorithms for NP-complete problems on planar graphs
1994/01/02 by Brenda S. Baker · 975 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Citation #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Discrete mathematics #Graph #Mathematics #NP-complete #Planar #Planar graph #Theoretical computer science #Time complexity #World Wide Web
paper · pdf · doi:10.1145/174644.174650
published in Journal of the ACM 41(1), 153-180 (Association for Computing Machinery)
openalex publication_date 1994/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
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
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 graphs
- Geometry based heuristics for unit disk graphs
- Minimum Vertex Cover in Rectangle Graphs
- Dynamic Meta-Kernelization
- PACE Solver Description: twinwidthfmi
- 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 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 nowhere dense graphs
- Induced Minors, Asymptotic Dimension, and Baker's Technique
- Optimal Coalition Structures in Cooperative Graph Games
- An nO(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 B2-VPG graphs into outer-string and co-comparability graphs
- Computing bounded-width tree and branch decompositions of k-outerplanar 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
- Triangle-free planar graphs with small independence number
- Dominating Set Knapsack: Profit Optimization on Dominating Sets
- Algorithmic Aspects of Upper Domination
- Combinatorial Auctions with Restricted Complements
- Courcelle's Theorem for Lipschitz Continuity
- Computational topology of graphs on surfaces
- Distributed Dominating Sets on Grids
- Complexity of Metric Dimension on Planar Graphs
- Parametric Graph Templates: Properties and Algorithms
- Local tree-width, excluded minors, and approximation algorithms
- Approximation Schemes for Covering and Packing
- Sublinear separators, fragility and subexponential expansion
- Independent sets in edge-clique graphs
- Minimum Makespan Multi-vehicle Dial-a-Ride
- Approximate Light Spanners in Planar Graphs
- Approximating MIS over equilateral B1-VPG graphs
- Approximation algorithms and hardness for domination with propagation
- Obtaining a Planar Graph by Vertex Deletion
- Partial Domination in Some Geometric Intersection Graphs and Some Complexity Results
- On distance r-dominating and 2r-independent sets in sparse graphs
- Stability of the Max-Weight Protocol in Adversarial Wireless Networks
- Computing the obstacle number of a plane graph
- Polynomial Time Data Reduction for Dominating Set
- On independence domination
- Capacitated Domination: Constant Factor Approximation for Planar Graphs
- An algorithmic weakening of the Erdős-Hajnal conjecture
- Bidimensional Parameters and Local Treewidth
- Deciding first-order properties of locally tree-decomposable structures
- Linearity of grid minors in treewidth with applications through bidimensionality
- Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
- On the Parameterized Complexity of Layered Graph Drawing
- An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree
- 3-packings in Triangulations: Algorithms, bounds, and Complexity
- Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- An optimal local approximation algorithm for max-min linear programs
- Planar graphs have bounded queue-number
- The Nature of Computation
- Invitation to Fixed-Parameter Algorithms
- Local Tree-Width, Excluded Minors, and Approximation Algorithms
- Fast Minor Testing in Planar Graphs
- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
- Diameter and Treewidth in Minor-Closed Graph Families, Revisited
- Diameter and Treewidth in Minor-Closed Graph Families
- A partial k-arboretum of graphs with bounded treewidth
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Maximum Clique Transversals
- Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
- On approximation properties of the Independent set problem for degree 3 graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Kernelization: Theory of Parameterized Preprocessing
- Linkless and flat embeddings in 3-space and the unknot problem
- Algorithms for Graphs Embeddable with Few Crossings per Edge
- On the Complexity of Metric Dimension
- Polynomial-time data reduction for dominating set
- Improved Approximation Algorithms for Relay Placement
- Approximation hardness of edge dominating set problems
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Learning and Optimization with Submodular Functions
- Prize-Collecting Steiner Tree and Forest in Planar Graphs
- The Bidimensionality Theory and Its Algorithmic Applications
- Clique Cover on Sparse Networks
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Some Recent Progress and Applications in Graph Minor Theory
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Planarity Allowing Few Error Vertices in Linear Time
- Independent set (graph theory) [wikipedia]
- Outerplanar graph [wikipedia]
- Planar separator theorem [wikipedia]
- 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