Recognition of Unit Segment and Polyline Graphs is $\exists\mathbb{R}$-Complete
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912753683267584 |
|---|---|
| author | Hoffmann, Michael Miltzow, Tillmann Weber, Simon Wulf, Lasse |
| author_facet | Hoffmann, Michael Miltzow, Tillmann Weber, Simon Wulf, Lasse |
| contents | Given a set of objects $O$ in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly $k$ bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as an intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are $\exists\mathbb{R}$-complete, leaving unit segments and polylines among the few remaining natural cases where the recognition complexity remained open. We show that recognition for both families of objects is $\exists\mathbb{R}$-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_02172 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recognition of Unit Segment and Polyline Graphs is $\exists\mathbb{R}$-Complete Hoffmann, Michael Miltzow, Tillmann Weber, Simon Wulf, Lasse Computational Geometry Given a set of objects $O$ in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly $k$ bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as an intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are $\exists\mathbb{R}$-complete, leaving unit segments and polylines among the few remaining natural cases where the recognition complexity remained open. We show that recognition for both families of objects is $\exists\mathbb{R}$-complete. |
| title | Recognition of Unit Segment and Polyline Graphs is $\exists\mathbb{R}$-Complete |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2401.02172 |