On complexity of mutlidistance graph recognition in ${\mathbb{R}}^1$

Abstract

Let $\mathcal{A}$ be a set of positive numbers. A graph $G$ is called an $\mathcal{A}$-embeddable graph in ${\mathbb{R}}^d$ if the vertices of $G$ can be positioned in ${\mathbb{R}}^d$ so that the distance between endpoints of any edge is an element of $\mathcal{A}$. We consider the computational problem of recognizing $\mathcal{A}$-embeddable graphs in ${\mathbb{R}}^1$ and classify all finite sets $\mathcal{A}$ by complexity of this problem in several natural variations.

38 pages, 9 figures. Extended abstract published in EUROCOMB'17 proceedings in Electronic Notes in Discrete Mathematics (http://www.sciencedirect.com/science/article/pii/S1571065317302354)