Fast recognition of planar non unit distance graphs

zbMATH Open1332.05046arXiv1401.4375MaRDI QIDQ3464032FDOQ3464032

Authors: Sascha Kurz 

Publication date: 20 January 2016

Abstract: We study criteria attesting that a given graph can not be embedded in the plane so that neighboring vertices are at unit distance apart and the straight line edges do not cross.

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

Recommendations

• scientific article; zbMATH DE number 759636
• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
• Distances in a rigid unit-distance graph in the plane
• Small unit-distance graphs in the plane
• Minimal graphs with respect to geometric distance realizability

zbMATH Keywords

planar graphsgraph embeddingsunit distance graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Cited In (11)

• Title not available (Why is that?)
• Distances in a rigid unit-distance graph in the plane
• On the maximum number of unit edges in \(K_{m,n}\)
• Planar unit-distance graphs having planar unit-distance complement
• A tight bound for the number of edges of matchstick graphs
• Small unit-distance graphs in the plane
• On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• On the computational complexity of degenerate unit distance representations of graphs
• Title not available (Why is that?)
• Involving \(d\)-convex simple and quasi-simple planar graphs in \(\mathbb R^3\)

This page was built for publication: Fast recognition of planar non unit distance graphs

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