Minimum face-spanning subgraphs of plane graphs

MaRDI QIDQ547549zbMATH OpenFDO

Authors Md. Mostofa Ali Patwary, Md. Saidur Rahman

Publication date 4 July 2011

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

connected vertex coverface-spanning subgraphsgraphsNP-complete problemsweighted tree cover

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Algorithms – ESA 2005
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
• On the two-connected planar spanning subgraph polytope
• On finding two-connected subgraphs in planar graphs
• Connected feedback vertex set in planar graphs

Cited in

(3)

• The minimum spanning subgraph problem with given cyclomatic number
• Complexity of minimum corridor guarding problems
• Connected feedback vertex set in planar graphs

This page was built for publication: Minimum face-spanning subgraphs of plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q547549)