On crossing numbers of geometric proximity graphs

DOI10.1016/J.COMGEO.2010.11.003MaRDI QIDQ632725zbMATH OpenOpenAlexFDO

Authors B. M. Ábrego, R. Fabila-Monroy, Silvia Fernández-Merchant, D. Flores-Peñaloza, Ferran Hurtado, Vera Sacristán, Maria Saumell

Publication date 25 March 2011

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2010.11.003

zbMATH Keywords

crossing numbergeometric graphsproximity graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Counting the number of crossings in geometric graphs
• Crossing numbers for certain distance graphs
• Counting and enumerating crossing-free geometric graphs
• Counting and enumerating crossing-free geometric graphs
• The Crossing Number of Graphs: Theory and Computation
• Number of crossing-free geometric graphs vs. Triangulations
• On crossing families of complete geometric graphs
• On the crossing number of almost planar graphs
• On the Crossing Number of Almost Planar Graphs
• On the crossing number of complete graphs

Cites work

• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• A central approach to bound the number of crossings in a generalized configuration
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING
• Graphs drawn with few crossings per edge
• Higher order Delaunay triangulations
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• Improved \(k\)-nearest neighbor classification
• Improved upper bounds on the crossing number
• Improving the crossing lemma by finding more crossings in sparse graphs
• New bounds on crossing numbers
• On a problem of P. Turan concerning graphs
• On structural and graph theoretic properties of higher order Delaunay graphs
• Optimization for first order Delaunay triangulations
• Pattern classification.
• Planar decompositions and the crossing number of graphs with an excluded minor
• Reduction of symmetric semidefinite programs using the regular -representation
• Research Problems in Discrete Geometry
• Towards a Theory of Geometric Graphs

Cited in

(10)

• Crossing numbers and stress of random graphs
• Counting the number of crossings in geometric graphs
• On crossing families of complete geometric graphs
• Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs
• The Rectilinear Crossing Number of a Complete Graph and Sylvester's "Four Point Problem" of Geometric Probability
• Limiting Crossing Numbers for Geodesic Drawings on the Sphere
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• Graph product structure for non-minor-closed classes
• Some properties of k-Delaunay and k-Gabriel graphs
• On the edge crossing properties of Euclidean minimum weight Laman graphs

Describes a project that uses

Uses Software

• GVF

This page was built for publication: On crossing numbers of geometric proximity graphs

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