Subgraph Isomorphism in Planar Graphs and Related Problems
From MaRDI portal
Publication:4505015
DOI10.7155/jgaa.00014zbMath0949.05055OpenAlexW2092904196WikidataQ56270748 ScholiaQ56270748MaRDI QIDQ4505015
Publication date: 19 September 2000
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/232204
Dynamic programming (90C39) Semimodular lattices, geometric lattices (06C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (70)
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Minimum Cuts in Surface Graphs ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Six-Critical Graphs on the Klein Bottle ⋮ Parameterized Graph Cleaning Problems ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ The complexity of multiple handed self-assembly ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Parameterized counting of trees, forests and matroid bases ⋮ Layered separators in minor-closed graph classes with applications ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ Polynomial algorithms for open plane graph and subgraph isomorphisms ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Graph-Based Generation of Referring Expressions ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ On low tree-depth decompositions ⋮ Cleaning interval graphs ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Approximating sparse quadratic programs ⋮ Obtaining a planar graph by vertex deletion ⋮ Feature-based 3D morphing based on geometrically constrained spherical parameterization ⋮ Parameterized two-player Nash equilibrium ⋮ On fractional fragility rates of graph classes ⋮ A note on the bounded fragmentation property and its applications in network reliability ⋮ Are unique subgraphs not easier to find? ⋮ Extended dynamic subgraph statistics using \(h\)-index parameterized data structures ⋮ Chordal embeddings of planar graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Subgraph isomorphism in graph classes ⋮ Faster parameterized algorithms for minor containment ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Coloring Triangle-Free Graphs on Surfaces ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ On triangulating \(k\)-outerplanar graphs ⋮ A convex relaxation bound for subgraph isomorphism ⋮ A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Parameterized graph cleaning problems ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Shortest-path queries in static networks ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ A simple algorithm for 4-coloring 3-colorable planar graphs ⋮ Slightly Superexponential Parameterized Problems ⋮ Five-coloring graphs on the Klein bottle ⋮ Unnamed Item ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Computing the Overlaps of Two Maps ⋮ Notes on tree- and path-chromatic number ⋮ Unique subgraphs are not easier to find ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Plane graphs of diameter two are 2-optimal ⋮ Treewidth of planar graphs: connections with duality
This page was built for publication: Subgraph Isomorphism in Planar Graphs and Related Problems
