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

DOI10.1016/J.TCS.2016.04.034MaRDI QIDQ290522zbMATH OpenOpenAlexFDO

Authors Emilio Di Giacomo, Giuseppe Liotta, 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 subgraphsinduced outerplanar graphstriconnected planar graphs

Mathematics Subject Classification ID

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

Recommendations

• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Long induced paths in graphs
• Long induced paths in 3-connected planar graphs
• Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
• Paths with restricted degrees of their vertices in planar graphs

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Dual of Dilworth's Decomposition Theorem
• Algorithms for maximum weight induced paths
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• Graph-Theoretic Concepts in Computer Science
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Long induced paths in 3-connected planar graphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Maximum induced trees in graphs
• On the hardness of approximating minimization problems
• Output-sensitive reporting of disjoint paths
• Schnyder woods and orthogonal surfaces
• Some results on graphs without long induced paths
• Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs
• The complexity of coloring graphs without long induced paths
• Untangling a planar graph

Cited in

(13)

• Invulnerability of planar two-tree networks
• Long induced paths in 3-connected planar graphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Long induced paths in minor-closed graph classes and beyond
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• On exact solution approaches for the longest induced path problem
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Morphing triangle contact representations of triangulations
• Structural parameters of Schnyder woods
• Monotone drawings of graphs with few directions
• Long induced paths in graphs
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
• Schnyder Woods and long induced paths in 3-connected planar graphs

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

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