The logic engine and the realization problem for nearest neighbor graphs

DOI10.1016/S0304-3975(97)84223-5zbMath0874.68235OpenAlexW2069814870MaRDI QIDQ1349880

Peter Eades, S. H. Whitesides

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)84223-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges ⋮ The strength of weak proximity ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ On arrangements of orthogonal circles ⋮ On the Computational Complexity of Degenerate Unit Distance Representations of Graphs ⋮ Complexity results for three-dimensional orthogonal graph drawing ⋮ Complexity dichotomy on partial grid recognition ⋮ Isometric Diamond Subgraphs ⋮ How to fit a tree in a box ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs

Cites Work

• Unnamed Item
• Realizability of Delaunay triangulations
• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• Algorithms for drawing graphs: An annotated bibliography
• Fixed edge-length graph drawing is NP-hard
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Computing proximity drawings of trees in the 3-dimensional space