4 citations · 6 across the 2 of their papers we have counts for
2 papers
cs.CG2014★ 4 cited
Planar Induced Subgraphs of Sparse Graphs
Glencora Borradaile, David Eppstein, Pingan Zhu
We show that every graph has an induced pseudoforest of at least vertices, an induced partial 2-tree of at least vertices, and an induced planar subgraph of at le…
cs.DS2014★ 2 cited
Lower bounds for testing digraph connectivity with one-pass streaming algorithms
Glencora Borradaile, Claire Mathieu, Theresa Migler
In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex to all vertices - each require a working memory of o…