David Eppstein - Publications

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.

  (Slides)

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

Semi-automatically filtered from a common source file.