Lower and upper bounds for long induced paths in 3-connected planar graphs
DOI10.1016/J.TCS.2016.04.034zbMATH Open1342.05071OpenAlexW2398969070MaRDI QIDQ290522FDOQ290522
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- A Dual of Dilworth's Decomposition Theorem
- Some results on graphs without long induced paths
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- Untangling a planar graph
- Maximum induced trees in graphs
- Output-sensitive reporting of disjoint paths
- Algorithms for maximum weight induced paths
- The complexity of coloring graphs without long 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
- Graph-Theoretic Concepts in Computer Science
- Schnyder woods and orthogonal surfaces
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
- Schnyder Woods and long induced paths in 3-connected planar graphs
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
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)
