The Complexity of Drawing Graphs on Few Lines and Few Planes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929260192595968 |
|---|---|
| author | Chaplick, Steven Fleszar, Krzysztof Lipp, Fabian Ravsky, Alexander Verbitsky, Oleg Wolff, Alexander |
| author_facet | Chaplick, Steven Fleszar, Krzysztof Lipp, Fabian Ravsky, Alexander Verbitsky, Oleg Wolff, Alexander |
| contents | It is well known that any graph admits a crossing-free straight-line drawing in $\mathbb{R}^3$ and that any planar graph admits the same even in $\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let $ρ^1_d(G)$ denote the smallest number of lines in $\mathbb{R}^d$ whose union contains a crossing-free straight-line drawing of $G$. For $d=2$, $G$ must be planar. Similarly, let $ρ^2_3(G)$ denote the smallest number of planes in $\mathbb{R}^3$ whose union contains a crossing-free straight-line drawing of $G$.
We investigate the complexity of computing these three parameters and obtain the following hardness and algorithmic results.
- For $d\in\{2,3\}$, we prove that deciding whether $ρ^1_d(G)\le k$ for a given graph $G$ and integer $k$ is ${\exists\mathbb{R}}$-complete.
- Since $\mathrm{NP}\subseteq{\exists\mathbb{R}}$, deciding $ρ^1_d(G)\le k$ is NP-hard for $d\in\{2,3\}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$.
- Since ${\exists\mathbb{R}}\subseteq\mathrm{PSPACE}$, both $ρ^1_2(G)$ and $ρ^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $ρ^1_2$ or $ρ^1_3$ sometimes require irrational coordinates.
- We prove that deciding whether $ρ^2_3(G)\le k$ is NP-hard for any fixed $k \ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $\mathrm{P}=\mathrm{NP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1607_06444 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | The Complexity of Drawing Graphs on Few Lines and Few Planes Chaplick, Steven Fleszar, Krzysztof Lipp, Fabian Ravsky, Alexander Verbitsky, Oleg Wolff, Alexander Computational Complexity Computational Geometry It is well known that any graph admits a crossing-free straight-line drawing in $\mathbb{R}^3$ and that any planar graph admits the same even in $\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let $ρ^1_d(G)$ denote the smallest number of lines in $\mathbb{R}^d$ whose union contains a crossing-free straight-line drawing of $G$. For $d=2$, $G$ must be planar. Similarly, let $ρ^2_3(G)$ denote the smallest number of planes in $\mathbb{R}^3$ whose union contains a crossing-free straight-line drawing of $G$. We investigate the complexity of computing these three parameters and obtain the following hardness and algorithmic results. - For $d\in\{2,3\}$, we prove that deciding whether $ρ^1_d(G)\le k$ for a given graph $G$ and integer $k$ is ${\exists\mathbb{R}}$-complete. - Since $\mathrm{NP}\subseteq{\exists\mathbb{R}}$, deciding $ρ^1_d(G)\le k$ is NP-hard for $d\in\{2,3\}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${\exists\mathbb{R}}\subseteq\mathrm{PSPACE}$, both $ρ^1_2(G)$ and $ρ^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $ρ^1_2$ or $ρ^1_3$ sometimes require irrational coordinates. - We prove that deciding whether $ρ^2_3(G)\le k$ is NP-hard for any fixed $k \ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $\mathrm{P}=\mathrm{NP}$. |
| title | The Complexity of Drawing Graphs on Few Lines and Few Planes |
| topic | Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/1607.06444 |