Document
type: Class

Counting the number of crossings in geometric graphs
crisid: 6724
most specific type: Article
freetext keyword: Algorithms; Geometric graphs; Graph drawings; Rectilinear crossing number Geometry; Graph algorithms; Graph theory; Convex geometric graphs; Geometric graphs; Layered graphs; Points in general position; Straight-line segments; Time algorithms; Graph structures
type: Entity
doi: 10.1016/j.ipl.2020.106028
date time value: article date 6724
type: Generically Dependent Continuant
type: Information Content Entity
type: Document
type: Thing
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(n2log⁡n) time algorithm to compute the number of pairs of edges that cross in a geometric graph on n vertices. For layered graphs and convex geometric graphs the algorithm takes O(n2) time. © 2020 Elsevier B.V.
type: Continuant
e iscopus: 2-s2.0-85091480833
type: Article
estado: published
origen: scopus
related by: authorship_44056
has funding vehicle: Horizon 2020 Framework Programme, H2020: 734922
has funding vehicle: 253261
related by: authorship_44058
has funding vehicle: 265667
artnum: 106028
accesstype: All Open Access, Green
most specific type: Document
related by: authorship_44057
related by: authorship_44059
has publication venue: Information Processing Letters
volume: 165

265667
type: Relationship
type: BFO_0000020
type: Entity
type: Thing
type: Grant
type: Continuant
funding vehicle for: Counting the number of crossings in geometric graphs

Continuant
type: Class

Entity
type: Class

Generically Dependent Continuant
type: Class

RDF description of Counting the number of crossings in geometric graphs - http://orbis.uaslp.mx/vivo/individual/scopus6723
rights: termsOfUse
date: 2026-08-27T07:40:44
publisher: vivo
type: Document

253261
type: Relationship
type: BFO_0000020
type: Entity
type: Thing
type: Grant
type: Continuant
funding vehicle for: Counting the number of crossings in geometric graphs

Article
type: Class

Information Content Entity
type: Class

Horizon 2020 Framework Programme, H2020: 734922
type: Relationship
type: BFO_0000020
type: Entity
type: Thing
type: Grant
type: Continuant
funding vehicle for: Counting the number of crossings in geometric graphs

Information Processing Letters
type: Continuant
publication venue for: Counting the number of crossings in geometric graphs
type: Information Content Entity
type: Entity
type: Document
type: Thing
type: Periodical
type: Journal
type: Collection
type: Generically Dependent Continuant