On embeddability of unit disk graphs onto straight lines

DOI10.1007/s00224-022-10110-yzbMath1512.05297arXiv1811.09881MaRDI QIDQ6038709

Onur Çağırıcı

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

zbMATH Keywords

NP-completeness; recognition; unit disk graph; restricted domain

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)