On the Complexity of Covering Vertices by Faces in a Planar Graph

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

zbMATH Keywords

complexity; embedding; planar graph; Steiner tree; polynomial-time recognition algorithm

Mathematics Subject Classification ID

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

Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time, 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