Subgraphs of 4-regular planar graphs

DOI10.1007/S00453-010-9435-8zbMATH Open1228.05126arXiv1101.5294OpenAlexW2016898545MaRDI QIDQ644803FDOQ644803

Authors: Chris Dowden, Louigi Addario-Berry 

Publication date: 7 November 2011

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Asymptotic enumeration and limit laws of planar graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Random planar graphs
• Dividing a Graph into Triconnected Components
• Random planar graphs with \(n\) nodes and a fixed number of edges
• Finding a \(\Delta\)-regular supergraph of minimum order
• Generating labeled planar graphs uniformly at random

Cited In (5)

• Random planar graphs with bounds on the maximum and minimum degrees
• Planar Hypohamiltonian Graphs on 40 Vertices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial time algorithms for two classes of subgraph problem

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)