**Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets**.

G. Borradaile and D. Eppstein.

arXiv:1206.2254.

*24th Canadian Conference on Computational Geometry (CCCG 2012)*, Prince Edward Island, Canada, 2012, pp. 311–316.

*Comp. Geom. Theory & Applications*49: 8–16, 2015 (special issue for CCCG 2012).When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

**Planar induced subgraphs of sparse graphs**.

G. Borradaile, D. Eppstein, and P. Zhu.

arXiv:1408.5939.

*22nd Int. Symp. Graph Drawing*, Würzburg, Germany, 2014.

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 1–12.

*J. Graph Algorithms & Applications*19 (1): 281–297, 2015.We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that

*m*/5.22 vertices are sufficient and*m*/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.**All-pairs minimum cuts in near-linear time for surface-embedded graphs**.

G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen.

arXiv:1411.7055.

*Proc. 32nd Int. Symp. Computational Geometry*, Boston, 2016.

Leibniz International Proceedings in Informatics (LIPIcs) 51, pp. 22:1–22:16.

We give the first known near-linear algorithms for constructing Gomory–Hu trees of bounded-genus graphs, and we shave a log off the time for the same problem on planar graphs.

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.