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