Connecting face hitting sets in planar graphs

DOI10.1016/J.IPL.2010.10.008MaRDI QIDQ1944026zbMATH OpenOpenAlexFDO

Authors P. Schweitzer, Patrick Schweitzer

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.10.008

zbMATH Keywords

combinatorial problemsface hitting setplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• On obstructions to small face covers in planar graphs
• Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
• Connected feedback vertex set in planar graphs
• The radius of k-connected planar graphs with bounded faces
• Subgraphs with restricted degrees of their vertices in planar graphs

Cites work

• A Linear Kernel for Planar Feedback Vertex Set
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Connected feedback vertex set in planar graphs
• FPT algorithms for connected feedback vertex set
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the minimum corridor connection problem and other generalized geometric problems
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

Cited in

(8)

• On obstructions to small face covers in planar graphs
• Complete metrics of bounded curvature on noncompact manifolds
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• The price of connectivity for cycle transversals
• The price of connectivity for feedback vertex set
• Splitting plane graphs to outerplanarity
• Splitting plane graphs to outerplanarity
• The price of connectivity for cycle transversals

This page was built for publication: Connecting face hitting sets in planar graphs

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