Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)
New isomorphic subgraph problems IES (edge-induced) and INS (node-induced) are investigated and their NP-completeness is proved for the general case and for numerous special cases of graphs. The investigated problems are seen as the general tools for demonstrating a symmetry of a graph. Finding two maximal edge-induced or node-induced graphs seems to be really the general criterion for demonstrating an internal structure of a graph. Therefore, the author claims that splitting a graph for two maximal isomorphic subgraphs and a remineder can be used as a foundation for graph drawing, he is going to develop layout for graph visualization using the isomorphic subgraph approach. There is also given a short survey of graph isomorphism and related problems. However, treating CLIQUE or HAMILTIONIAN as special cases of subgraph isomorphism seems to be arbitrary and usable only for very restricted claims. For the entire collection see [Zbl 0931.00046].
- Drawing series parallel digraphs symmetrically
- Computing and Drawing Isomorphic Subgraphs
- Computing and drawing isomorphic subgraphs
- Isomorphic edge disjoint subgraphs of hypergraphs
- Subgraph isomorphism on graph classes that exclude a substructure
- Subgraph isomorphism on graph classes that exclude a substructure
This page was built for publication: Isomorphic subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501707)
