Algorithms for finding an induced cycle in planar graphs

DOI10.1007/s00493-010-2499-xzbMath1240.05291OpenAlexW1989836886MaRDI QIDQ653839

Yusuke Kobayashi, Ken-ichi Kawarabayashi

Publication date: 19 December 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2499-x

zbMATH Keywords

algorithmholeplanar graphinduced cycle

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item, A faster algorithm to recognize even-hole-free graphs

Cites Work

• Graph minors. XXII. Irrelevant vertices in linkage problems
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• The strong perfect graph theorem
• Induced disjoint paths problem in a planar digraph
• Graph minors. VII: Disjoint paths on a surface
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the complexity of testing for odd holes and induced odd paths
• Graph minors. XI: Circuits on a surface
• Induced circuits in planar graphs
• Quickly excluding a planar graph
• Rooted routing in the plane
• The complexity of induced minors and related problems
• Graph minors. XIII: The disjoint paths problem
• Recognizing Berge graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• The Induced Disjoint Paths Problem
• Detecting even holes
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Unnamed Item
• Unnamed Item