Publication:5111733

DOI10.4230/LIPIcs.ESA.2017.44zbMath1442.68171MaRDI QIDQ5111733

Pan Peng, Monika R. Henzinger, Gramoz Goranci

Publication date: 27 May 2020

zbMATH Keywords

reachability; planar graphs; metric embedding; graph sparsification; vertex sparsification

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C22: Signed and weighted graphs

68R12: Metric embeddings as related to computational problems and algorithms