Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.17504 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911932107194368 |
|---|---|
| author | Cardinal, Jean |
| author_facet | Cardinal, Jean |
| contents | We consider the complexity of the recognition problem for two families of combinatorial structures. A graph $G=(V,E)$ is said to be an intersection graph of lines in space if every $v\in V$ can be mapped to a straight line $\ell (v)$ in $\mathbb{R}^3$ so that $vw$ is an edge in $E$ if and only if $\ell(v)$ and $\ell(w)$ intersect. A partially ordered set $(X,\prec)$ is said to be a circle order, or a 2-space-time order, if every $x\in X$ can be mapped to a closed circular disk $C(x)$ so that $y\prec x$ if and only if $C(y)$ is contained in $C(x)$. We prove that the recognition problems for intersection graphs of lines and circle orders are both $\exists\mathbb{R}$-complete, hence polynomial-time equivalent to deciding whether a system of polynomial equalities and inequalities has a solution over the reals. The second result addresses an open problem posed by Brightwell and Luczak. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17504 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity of Intersection Graphs of Lines in Space and Circle Orders Cardinal, Jean Computational Geometry Discrete Mathematics We consider the complexity of the recognition problem for two families of combinatorial structures. A graph $G=(V,E)$ is said to be an intersection graph of lines in space if every $v\in V$ can be mapped to a straight line $\ell (v)$ in $\mathbb{R}^3$ so that $vw$ is an edge in $E$ if and only if $\ell(v)$ and $\ell(w)$ intersect. A partially ordered set $(X,\prec)$ is said to be a circle order, or a 2-space-time order, if every $x\in X$ can be mapped to a closed circular disk $C(x)$ so that $y\prec x$ if and only if $C(y)$ is contained in $C(x)$. We prove that the recognition problems for intersection graphs of lines and circle orders are both $\exists\mathbb{R}$-complete, hence polynomial-time equivalent to deciding whether a system of polynomial equalities and inequalities has a solution over the reals. The second result addresses an open problem posed by Brightwell and Luczak. |
| title | The Complexity of Intersection Graphs of Lines in Space and Circle Orders |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2406.17504 |