Abstract: We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^{2.5}) and can be used to find an explicit 4-regular planar graph G containing H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.
Recommendations
Cites work
- Asymptotic enumeration and limit laws of planar graphs
- Dividing a Graph into Triconnected Components
- Finding a \(\Delta\)-regular supergraph of minimum order
- Generating labeled planar graphs uniformly at random
- Random planar graphs
- Random planar graphs with \(n\) nodes and a fixed number of edges
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Cited in
(5)- scientific article; zbMATH DE number 1877028 (Why is no real title available?)
- Random planar graphs with bounds on the maximum and minimum degrees
- scientific article; zbMATH DE number 4189750 (Why is no real title available?)
- Polynomial time algorithms for two classes of subgraph problem
- Planar Hypohamiltonian Graphs on 40 Vertices
This page was built for publication: Subgraphs of 4-regular planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644803)
