Counting the number of crossings in geometric graphs

DOI10.1016/J.IPL.2020.106028MaRDI QIDQ2224846zbMATH OpenOpenAlexFDO

Authors R. Fabila-Monroy, César Hernández-Vélez, Carlos Hidalgo-Toscano, Frank Duque

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphsgraph drawingsrectilinear crossing number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^{2}logn)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time.

Recommendations

• Counting and enumerating crossing-free geometric graphs
• Counting and enumerating crossing-free geometric graphs
• Number of crossing-free geometric graphs vs. Triangulations
• On crossing numbers of geometric proximity graphs
• Crossing numbers of graphs
• The Crossing Number of Graphs: Theory and Computation
• Survey of the crossing number of graphs
• On the crossing number of complete graphs
• On the crossing number of complete graphs

Cites work

• A central approach to bound the number of crossings in a generalized configuration
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Computational geometry. Algorithms and applications.
• Computational search of small point sets with small rectilinear crossing number
• Counting k-subsets and convex k-gons in the plane
• Cutting hyperplanes for divide-and-conquer
• Graph Drawing

Cited in

(8)

• Counting triangulations and other crossing-free structures approximately
• scientific article; zbMATH DE number 4158672 (Why is no real title available?)
• Reporting the crossing-free segments of a complete geometric graph
• Linear-time algorithms for geometric graphs with sublinearly many crossings
• Limiting Crossing Numbers for Geodesic Drawings on the Sphere
• Linear-time algorithms for geometric graphs with sublinearly many edge crossings
• On crossing numbers of geometric proximity graphs
• On the rectilinear crossing number of complete balanced multipartite graphs and balanced layered graphs

This page was built for publication: Counting the number of crossings in geometric graphs

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