On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
From MaRDI portal
Publication:1690053
DOI10.1016/j.endm.2017.07.070zbMath1378.05088arXiv1710.05140OpenAlexW2744474468MaRDI QIDQ1690053
Publication date: 18 January 2018
Full work available at URL: https://arxiv.org/abs/1710.05140
Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (2)
Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs ⋮ Estimate of the number of edges in special subgraphs of a distance graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turán type results for distance graphs
- Sphere and dot product representations of graphs
- On the complexity of H-coloring
- The complexity of minimizing wire lengths in VLSI layouts
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Graph homomorphisms with infinite targets
- The logic engine and the realization problem for nearest neighbor graphs
- Unit disk graph recognition is NP-hard
- On computational complexity of length embeddability of graphs
- Borsuk's problem and the chromatic numbers of some metric spaces
- Coloring Distance Graphs and Graphs of Diameters
- Realizability of Graphs and Linkages
- On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
- On Sets of Distances of n Points
This page was built for publication: On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
