English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The notion of shortcut partition, introduced recently by Chang, Conroy, Le,Milenkovi\'c, Solomon, and Than [CCLMST23], is a new type of graph partitioninto low-diameter clusters. Roughly speaking, the shortcut partition guaranteesthat for every two vertices $u$ and $v$ in the graph, there exists a pathbetween $u$ and $v$ that intersects only a few clusters. They proved that anyplanar graph admits a shortcut partition and gave several applications,including a construction of tree cover for arbitrary planar graphs with stretch$1+\varepsilon$ and $O(1)$ many trees for any fixed $\varepsilon \in (0,1)$.However, the construction heavily exploits planarity in multiple steps, and isthus inherently limited to planar graphs.  In this work, we breach the "planarity barrier" to construct a shortcutpartition for $K_r$-minor-free graphs for any $r$. To this end, we take acompletely different approach -- our key contribution is a novel deterministicvariant of the cop decomposition in minor-free graphs [And86, AGG14]. Ourshortcut partition for $K_r$-minor-free graphs yields several directapplications. Most notably, we construct the first optimal distance oracle for$K_r$-minor-free graphs, with $1+\varepsilon$ stretch, linear space, andconstant query time for any fixed $\varepsilon \in (0,1)$. The previous bestdistance oracle [AG06] uses $O(n\log n)$ space and $O(\log n)$ query time, andits construction relies on Robertson-Seymour structural theorem and othersophisticated tools. We also obtain the first tree cover of $O(1)$ size forminor-free graphs with stretch $1+\varepsilon$, while the previous best$(1+\varepsilon)$-tree cover has size $O(\log^2 n)$ [BFN19].

Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More