We show that the maximum flow problem can be solved in near-linear time for K5-minor-free and K3,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.
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.