On the complexity of graph embeddings

DOI10.1007/3-540-57155-8_251MaRDI QIDQ5060116zbMATH OpenOpenAlexFDO

Authors Saroja P. Kanchi, Arkady Kanevsky, Jianer Chen

Publication date 18 January 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57155-8_251

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• A note on approximating graph genus
• scientific article; zbMATH DE number 867666
• Algorithmic graph embeddings
• scientific article; zbMATH DE number 4142064
• Embedding graphs into two-dimensional simplicial complexes

Cites work

• Hierarchy for imbedding-distribution invariants of a graph
• How to determine the maximum genus of a graph
• scientific article; zbMATH DE number 3906520 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Local extrema in genus-stratified graphs
• The graph genus problem is NP-complete

Cited in

(17)

• Algorithmic graph embeddings
• Proceedings of the conference ``Embedded graphs
• A tight lower bound on the maximum genus of a simplicial graph
• A note on approximating graph genus
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• scientific article; zbMATH DE number 3843669 (Why is no real title available?)
• scientific article; zbMATH DE number 4142064 (Why is no real title available?)
• scientific article; zbMATH DE number 4126319 (Why is no real title available?)
• scientific article; zbMATH DE number 475582 (Why is no real title available?)
• scientific article; zbMATH DE number 867666 (Why is no real title available?)
• High-Speed and Noise-Robust Embedding of Hypergraphs Based on Double-Centered Incidence Matrix
• Embedding graphs into two-dimensional simplicial complexes
• On Whole-Graph Embedding Techniques
• scientific article; zbMATH DE number 7662167 (Why is no real title available?)
• Graph Drawing
• Algorithmic graph embeddings
• Complexity issues in color-preserving graph embeddings

This page was built for publication: On the complexity of graph embeddings

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