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

DOI10.1137/0217004zbMath0646.68085OpenAlexW2040444410MaRDI 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

complexityembeddingplanar graphSteiner treepolynomial-time recognition algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (23)

Efficient parallel algorithms for shortest paths in planar graphs ⋮ Linear-time algorithms for problems on planar graphs with fixed disk dimension ⋮ Efficient distributed algorithms for single-source shortest paths and related problems on plane networks ⋮ 3-connected reduction for regular graph covers ⋮ Planar Embeddings with Small and Uniform Faces ⋮ Jordan-like characterization of automorphism groups of planar graphs ⋮ Splitting plane graphs to outerplanarity ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ 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 ⋮ Advice classes of parametrized tractability ⋮ Obstruction sets for outer-cylindrical graphs ⋮ Efficient parallel algorithms for shortest paths in planar digraphs ⋮ On obstructions to small face covers in planar graphs ⋮ 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 ⋮ A bounded search tree algorithm for parameterized face cover ⋮ Graph isomorphism restricted by lists ⋮ Refined Vertex Sparsifiers of 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

This page was built for publication: On the Complexity of Covering Vertices by Faces in a Planar Graph