An asymptotic upper bound for graph embeddings

DOI10.1016/j.dam.2022.12.010zbMath1506.05141OpenAlexW4313367953MaRDI QIDQ2112663

Charalambos Tzamos, Evangelos Bartzos, Ioannis Z. Emiris

Publication date: 11 January 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.12.010

zbMATH Keywords

upper boundgraph embeddinggraph orientationLaman graphminimally rigid graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• Bezout
• LamanGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On symmetric and skew-symmetric determinantal varieties
• The m-Bézout bound and distance geometry
• Minimal NMR distance information for rigidity of protein graphs
• The number of embeddings of minimally rigid graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• New upper bounds for the number of embeddings of minimally rigid graphs
• Counting realizations of Laman graphs on the sphere
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• On graphs and rigidity of plane skeletal structures
• The Rigidity of Graphs
• The Number of Realizations of a Laman Graph

This page was built for publication: An asymptotic upper bound for graph embeddings