Complexity of graph embeddability problems

DOI10.1016/0304-3975(81)90085-2zbMath0459.68027OpenAlexW2010162515MaRDI QIDQ1152224

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

time complexityplanar graphcombinatorial 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)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A topological space for which graph embeddability is undecidable
• A comparison of polynomial time reducibilities
• The complexity of theorem-proving procedures
• Recursively enumerable sets of positive integers and their decision problems

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