Lower and upper bounds for long induced paths in 3-connected planar graphs

DOI10.1016/j.tcs.2016.04.034zbMath1342.05071OpenAlexW2398969070MaRDI QIDQ290522

Giuseppe Liotta, Emilio Di Giacomo, Tamara Mchedlidze

Publication date: 1 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.034

zbMATH Keywords

induced subgraphstriconnected planar graphsinduced outerplanar graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Morphing triangle contact representations of triangulations ⋮ Long induced paths in minor-closed graph classes and beyond ⋮ Invulnerability of planar two-tree networks ⋮ Monotone drawings of graphs with few directions ⋮ Long induced paths in graphs ⋮ On exact solution approaches for the longest induced path problem ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size

Cites Work

• Schnyder woods and orthogonal surfaces
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Some results on graphs without long induced paths
• Untangling a planar graph
• Maximum induced trees in graphs
• Output-sensitive reporting of disjoint paths
• Algorithms for maximum weight induced paths
• Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs
• Long induced paths in 3-connected planar graphs
• On the hardness of approximating minimization problems
• A Dual of Dilworth's Decomposition Theorem
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower and upper bounds for long induced paths in 3-connected planar graphs