Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings

DOI10.1137/090759112zbMath1209.68626arXiv0812.0893OpenAlexW2762701907MaRDI QIDQ5390616

Darren Strash, David Eppstein, Michael T. Goodrich

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

arrangementsgeometric graphsshortest pathsVoronoi diagramsepsilon-cuttingstrapezoidal maps

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

This page was built for publication: Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings