David Eppstein - Publications

Publications with Erin Chambers

• Flows in one-crossing-minor-free graphs.
  E. Chambers and D. Eppstein.
  arXiv:1007.1484.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Lecture Notes in Comp. Sci. 6506, 2010, pp. 241-252, Springer-Verlag.
  J. Graph Algorithms and Applications 17 (3): 201-220, 2013.

  We show that the maximum flow problem can be solved in near-linear time for K₅-minor-free and K_3,3-minor-free graphs. The same result also holds for H-minor-free graphs when H can be embedded in the plane with one crossing and a structural decomposition of the input flow graph is given.

• Drawing graphs in the plane with a prescribed outer face and polynomial area.
  E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Lecture Notes in Comp. Sci. 6502, 2011, pp. 129-140, Springer-Verlag.
  arXiv:1009.0088.
  J. Graph Algorithms and Applications 16(2):243-259, 2012.

  Tutte's method of spring embeddings allows any triangulated planar graph to be drawn so that the outer face has any pre-specified convex shape, but it may place vertices exponentially close to each other. Alternative graph drawing methods provide polynomial-area straight line drawings but do not allow the outer face shape to be specified. We describe a drawing method that combines both properties: it has polynomial area, and can match any pre-specified shape of the outer face, even a shape in which some of the vertices have 180 degree angles. We apply our results to drawing polygonal schemas for graphs embedded on surfaces of positive genus.

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

Semi-automatically filtered from a common source file.