Short path queries in planar graphs in constant time

DOI10.1145/780542.780565zbMath1192.05164OpenAlexW2155694840MaRDI QIDQ3581292

Maciej Kurowski, Łukasz Kowalik

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780565

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (12)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ A substring-substring LCS data structure ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Unnamed Item ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ Fully dynamic MIS in uniformly sparse graphs ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ Strip planarity testing for embedded planar graphs ⋮ Many distances in planar graphs ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time

This page was built for publication: Short path queries in planar graphs in constant time