On the Complexity of Covering Vertices by Faces in a Planar Graph
From MaRDI portal
Publication:3790663
DOI10.1137/0217004zbMath0646.68085MaRDI QIDQ3790663
Bienstock, Daniel, Clyde l. Monma
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217004
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
Related Items
On the complexity of embedding planar graphs to minimize certain distance measures, Advice classes of parametrized tractability, Linear-time algorithms for problems on planar graphs with fixed disk dimension, A bounded search tree algorithm for parameterized face cover, Representations of graphs and networks (coding, layouts and embeddings), Polynomially solvable special cases of the Steiner problem in planar networks, The role of Steiner hulls in the solution to Steiner tree problems, Efficient parallel algorithms for shortest paths in planar digraphs, On obstructions to small face covers in planar graphs, A partial k-arboretum of graphs with bounded treewidth, Minimal connected enclosures on an embedded planar graph, Face covers and the genus problem for apex graphs, Obstruction sets for outer-cylindrical graphs, Efficient distributed algorithms for single-source shortest paths and related problems on plane networks
