Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908489624846336 |
|---|---|
| author | Lubiw, Anna Schaefer, Marcus |
| author_facet | Lubiw, Anna Schaefer, Marcus |
| contents | We show that the recognition problem for penny graphs (contact graphs of unit disks in the plane) is $\exists\mathbb{R}$-complete, that is, computationally as hard as the existential theory of the reals, even if a combinatorial plane embedding of the graph is given. The exact complexity of the penny graph recognition problem has been a long-standing open problem.
We lift the penny graph result to three dimensions and show that the recognition problem for marble graphs (contact graphs of unit balls in three dimensions) is $\exists\mathbb{R}$-complete.
Finally, we show that rigidity of penny graphs is $\forall\mathbb{R}$-complete and look at grid embeddings of penny graphs that are trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10136 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals Lubiw, Anna Schaefer, Marcus Computational Geometry 68Q17, 05C62 F.2.2 We show that the recognition problem for penny graphs (contact graphs of unit disks in the plane) is $\exists\mathbb{R}$-complete, that is, computationally as hard as the existential theory of the reals, even if a combinatorial plane embedding of the graph is given. The exact complexity of the penny graph recognition problem has been a long-standing open problem. We lift the penny graph result to three dimensions and show that the recognition problem for marble graphs (contact graphs of unit balls in three dimensions) is $\exists\mathbb{R}$-complete. Finally, we show that rigidity of penny graphs is $\forall\mathbb{R}$-complete and look at grid embeddings of penny graphs that are trees. |
| title | Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals |
| topic | Computational Geometry 68Q17, 05C62 F.2.2 |
| url | https://arxiv.org/abs/2508.10136 |