On the Computational Complexity of Degenerate Unit Distance Representations of Graphs

DOI10.1007/978-3-642-19222-7_28zbMath1326.68160arXiv1001.0886OpenAlexW2151636144WikidataQ56001751 ScholiaQ56001751MaRDI QIDQ3000515

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)

Related Items (4)

On computational complexity of length embeddability of graphs ⋮ On the distance and multidistance graph embeddability problem ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ Minimal graphs with respect to geometric distance realizability

Cites Work

• Unnamed Item
• Unnamed Item
• On the dimension to represent a graph by a unit distance graph
• On the Euclidean dimension of a wheel
• Note on induced subgraphs of the unit distance graph \(E^ n\)
• On the Euclidean dimension of a complete multipartite graph
• 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
• The logic engine and the realization problem for nearest neighbor graphs
• Fixed edge-length graph drawing is NP-hard
• Polycyclic configurations
• ALL GENERALIZED PETERSEN GRAPHS ARE UNIT-DISTANCE GRAPHS
• The Mathematical Coloring Book
• Conditions for Unique Graph Realizations
• On the dimension of a graph
• Graph Drawing

This page was built for publication: On the Computational Complexity of Degenerate Unit Distance Representations of Graphs