# The Complexity of Drawing Graphs on Few Lines and Few Planes

## DOI:

https://doi.org/10.7155/jgaa.00630## Keywords:

graph drawing , affine cover numbers , line cover number , plane cover number , complexity## Abstract

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 $\rho^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$, the graph $G$ must be planar. Similarly, let $\rho^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 $\rho^1_d(G)\le k$ for a given graph $G$ and integer $k$ is $\exists\mathbb{R}$-complete.
- Since $NP \subseteq \exists\mathbb{R}$, deciding $\rho^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 PSPACE$, both $\rho^1_2(G)$ and $\rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $\rho^1_2$ or $\rho^1_3$ sometimes require irrational coordinates.
- We prove that deciding whether $\rho^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 $P=NP$.

### Downloads

Download data is not yet available.

## Downloads

## Published

2023-07-01

## How to Cite

*Journal of Graph Algorithms and Applications*,

*27*(6), 459–488. https://doi.org/10.7155/jgaa.00630

## Issue

## Section

Articles

## Categories

## License

Copyright (c) 2023 Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff

This work is licensed under a Creative Commons Attribution 4.0 International License.