Subgraphs of 4-regular planar graphs

DOI10.1007/S00453-010-9435-8MaRDI QIDQ644803zbMATH OpenOpenAlexFDO

Authors Chris Dowden, Louigi Addario-Berry

Publication date 7 November 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.5294

zbMATH Keywords

planar graphssubgraph appearance

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

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

• Finding regular subgraphs in both arbitrary and planar graphs
• Polynomial time algorithms for two classes of subgraph problem
• scientific article; zbMATH DE number 1456823
• Publication:5753967
• scientific article; zbMATH DE number 3902701

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)