On embeddability of unit disk graphs onto straight lines
From MaRDI portal
Publication:6038709
DOI10.1007/s00224-022-10110-yzbMath1512.05297arXiv1811.09881OpenAlexW3012693387MaRDI QIDQ6038709
Publication date: 2 May 2023
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.09881
Analysis of algorithms and problem complexity (68Q25) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- Thin strip graphs
- Sphere and dot product representations of graphs
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Interval graphs and interval orders
- The complexity of minimizing wire lengths in VLSI layouts
- Unit disk graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Unit disk graph recognition is NP-hard
- On coloring unit disk graphs
- Integer realizations of disk and segment graphs
- Hamilton Paths in Grid Graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Recognizing a DOG is Hard but not when it is Thin and Unit
- Algorithmic Aspects of Wireless Sensor Networks
- The complexity of satisfiability problems
This page was built for publication: On embeddability of unit disk graphs onto straight lines
