On the computational complexity of degenerate unit distance representations of graphs

DOI10.1007/978-3-642-19222-7_28zbMATH Open1326.68160DBLPconf/iwoca/HorvatKP10OpenAlexW2151636144WikidataQ56001751 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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3845607 (Why is no real title available?)
• All generalized Petersen graphs are unit-distance graphs
• Conditions for Unique Graph Realizations
• Fixed edge-length graph drawing is NP-hard
• Graph Drawing
• Note on induced subgraphs of the unit distance graph \(E^ n\)
• On the Euclidean dimension of a complete multipartite graph
• On the Euclidean dimension of a wheel
• 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 dimension of a graph
• On the dimension to represent a graph by a unit distance graph
• Polycyclic configurations
• The Mathematical Coloring Book
• The logic engine and the realization problem for nearest neighbor graphs
• Unit distance representations of the Petersen graph in the plane.

Cited in

(7)

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

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)