**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.

Springer,*Lecture Notes in Comp. Sci.*6506, 2010, pp. 241–252.

*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

_{5}-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.

Springer,*Lecture Notes in Comp. Sci.*6502, 2011, pp. 129–140.

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.