On the computational complexity of degenerate unit distance representations of graphs

DOI10.1007/978-3-642-19222-7_28zbMATH Open1326.68160DBLPconf/iwoca/HorvatKP10arXiv1001.0886OpenAlexW2151636144WikidataQ56001751 ScholiaQ56001751MaRDI QIDQ3000515FDOQ3000515

Authors: Boris Horvat, Jan Kratochvíl, Tomaž Pisanski 

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Some graphs admit drawings in the Euclidean k-space in such a (natu- ral) way, that edges are represented as line segments of unit length. Such drawings will be called k dimensional unit distance representations. When two non-adjacent vertices are drawn in the same point, we say that the representation is degenerate. The dimension (the Euclidean dimension) of a graph is defined to be the minimum integer k needed that a given graph has non-degenerate k dimensional unit distance representation (with the property that non-adjacent vertices are mapped to points, that are not distance one appart). It is proved that deciding if an input graph is homomorphic to a graph with dimension k >= 2 (with the Euclidean dimension k >= 2) are NP-hard problems.

Full work available at URL: https://arxiv.org/abs/1001.0886

Recommendations

• On the dimension to represent a graph by a unit distance graph
• On computational complexity of length embeddability of graphs
• Unit distance representations of the Petersen graph in the plane.
• Fast recognition of planar non unit distance graphs
• On the distance and multidistance graph embeddability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• The Mathematical Coloring Book
• Conditions for Unique Graph Realizations
• Title not available (Why is that?)
• Polycyclic configurations
• Note on induced subgraphs of the unit distance graph \(E^ n\)
• On the dimension of a graph
• All generalized Petersen graphs are unit-distance graphs
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the Euclidean dimension of a complete multipartite graph
• The logic engine and the realization problem for nearest neighbor graphs
• Fixed edge-length graph drawing is NP-hard
• On the dimension to represent a graph by a unit distance graph
• On the Euclidean dimension of a wheel
• Title not available (Why is that?)
• Graph Drawing

Cited In (6)

• Complexity of recognizing multidistance graphs in \(\mathbb{R}^d\)
• Minimal graphs with respect to geometric distance realizability
• On the distance and multidistance graph embeddability problem
• Information theoretic measures of UHG graphs with low computational complexity
• On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
• On computational complexity of length embeddability of graphs

This page was built for publication: On the computational complexity of degenerate unit distance representations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000515)