Fast recognition of planar non unit distance graphs

MaRDI QIDQ3464032zbMATH OpenFDO

Authors Sascha Kurz

Publication date 20 January 2016

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

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)

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.

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

Cited in

(11)

• scientific article; zbMATH DE number 759636 (Why is no real title available?)
• Distances in a rigid unit-distance graph in the plane
• Planar unit-distance graphs having planar unit-distance complement
• On the maximum number of unit edges in \(K_{m,n}\)
• 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
• Involving \(d\)-convex simple and quasi-simple planar graphs in \(\mathbb R^3\)
• scientific article; zbMATH DE number 4106878 (Why is no real title available?)

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)