conference paper
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums
Amit Chakrabartia b, Alexander Jaffec, James R. Leec d, Justin Vincentc
- aDartmouth College Department of Computer Science, University of Washington, Hanover, NH, USA
- bDepartment of Computer Science, Dartmouth College, Hanover, NH
- cDepartment of Computer Science and Engineering, University of Washington, Seattle, WA
- dUCLA
Annual Symposium on Foundations of Computer ScienceInstitute of Electrical and Electronics Engineers2008-10-01 42 citations26 references
Looking for the full paper…
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We study the properties of embeddings, multicommodity flows, and sparse cuts in minor-closed families of graphs which are also closed under 2-sums; this includes planar graphs, graphs of bounded treewidth, and constructions based on recursive edge replacement.