Short path queries in planar graphs in constant time
From MaRDI portal
Publication:3581292
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
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