Publications with Bruce Reed
Finding maximal sets of laminar 3-separators in planar graphs in linear time.
D. Eppstein and B. Reed.
arXiv:1810.07825.
30th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2019, pp. 589–605.Given a 3-vertex-connected planar graph, we find a hierarchical decomposition of the graph by 3-vertex separators, such that each piece of the decomposition is 4-vertex-connected, in linear time. The result has applications to an algorithm of Kawarabayashi, Li, and Reed for finding disjoint paths in nonplanar graphs.