Complexity of graph embeddability problems

DOI10.1016/0304-3975(81)90085-2MaRDI QIDQ1152224zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1981

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(81)90085-2

zbMATH Keywords

planar graphtime complexitycombinatorial embeddability in infinite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3336804 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A topological space for which graph embeddability is undecidable
• Graph theory
• Recursively enumerable sets of positive integers and their decision problems
• The complexity of theorem-proving procedures

Cited in

(1)

• Algorithmic problems in right-angled Artin groups: complexity and applications

This page was built for publication: Complexity of graph embeddability problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1152224)