On Embeddability of Unit Disk Graphs onto Straight Lines

DOI10.1007/978-3-030-50026-9_13MaRDI QIDQ5042239zbMATH OpenOpenAlexFDO

Authors Onur Çağırıcı

Publication date 19 October 2022

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On embeddability of unit disk graphs onto straight lines
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• Good quality virtual realization of unit disk graphs

Cites work

• Encyclopedia of Optimization
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• Integer realizations of disk and segment graphs
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• Recognizing a DOG is hard, but not when it is thin and unit
• Sphere and dot product representations of graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of minimizing wire lengths in VLSI layouts
• The complexity of satisfiability problems
• Unit disk graph recognition is NP-hard
• Unit disk graphs

Cited in

(2)

• On a straight-line embedding problem of graphs
• Unit disk representations of embedded trees, outerplanar and multi-legged graphs

This page was built for publication: On Embeddability of Unit Disk Graphs onto Straight Lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042239)