Vi studerar den kvantitativa geometrin av grafer i termer av deras släkte, med hjälp av strukturen av vissa "klippta grafer", dvs.. Subgraphs vars borttagning lämnar en planar graf. I synnerhet ger vi optimala gränser för slumpmässiga partitionering system, liksom olika typer av inbäddningar. Med hjälp av dessa geometriska primitiver presenterar vi exponentiellt förbättrat beroende av släktet för ett antal problem som ungefärliga maxflöde/mincut teorem, approximationer för enhetliga och icke-uniforma sparest cut, trädbredd approximation, Laplacian eigen value gränses, och Lipschitz förlängning teorems och relaterade metrisk märkningsproblem. Vi listar här ett urval av dessa förbättringar. Alla följande uppgifter avser grafer av släktet g, om inget annat anges. • Vi visar att sådana diagram medger en O(log g)-ungefärlig multi-commodity max-flow/min-cut teorem för fallet med enhetliga krav. Denna gräns är optimal, och förbättras över den tidigare gränsen av O (g) [KPR93, FT03]. För allmänna krav visar vi att det värsta möjliga gapet är O(log g + C P ), där C P är gapet för planar grafer. Detta beroende är optimalt, och ger redan en gräns för O (log g + ε log n), förbättring över den tidigare gränsen av O ( • Vi ger en O ( ε log g) - approximation för den enhetliga glesaste snitt, balanserad vertex separator, och trädbredd problem, förbättring över föregående • Om en graf G har genus g och maximal grad D, visar vi att kth Laplacian eigenvärde av G är (log g) • Vi visar att om (X, d) är den kortaste-paten metrisk på en graf av genus g och S X, då varje Detta förbättras över den tidigare gränsen av O (Lg) [LN05], och jämför med en nedre gränsen av L ε log g). På ett relaterat sätt, visar vi att det finns en O (log g)- approximation för 0-extensionsproblemet på sådana grafer, förbättra över den tidigare O (g) bundna. • Vi visar att varje n-vertex kortaste-väg metrisk på en graf av genus g inbäddar i L 2 med distorsion O(log g + ε log n), förbättra över den tidigare gränsen av O ( ε g log n). Vårt resultat är asymptotiskt optimalt för varje beroende g = g(n).
De idéer som utvecklats i detta arbete leder till en asymptotiskt optimal stoppningsparameter för O(log g) för genus-g grafer REF.
Genus and the geometry of the cut graph
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}