# Structured Recursive Separator Decompositions for Planar Graphs in Linear Time

Philip N. Klein, Shay Mozes, and Christian Sommer
STOC 2013 - 45th ACM Symposium on Theory of Computing (pp. 505-514)

Given a planar graph $$G$$ on $$n$$ vertices and an integer parameter $$r \lt n$$, an $$r$$-division of $$G$$ with few holes is a decomposition of $$G$$ into $$O(n/r)$$ regions of size at most $$r$$ such that each region contains at most a constant number of faces that are not faces of $$G$$ (also called holes), and such that, for each region, the total number of vertices on these faces is $$O(\sqrt r)$$.

We provide a linear-time algorithm for computing $$r$$-divisions with few holes. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of $$G$$ that includes $$r$$-divisions for essentially all values of $$r$$. In particular, given an exponentially increasing sequence $$\mathbf{r} = (r_1, r_2,\dots)$$, our algorithm can produce a recursive $$\mathbf{r}$$-division with few holes in linear time.

$$r$$-divisions with few holes have been used in efficient algorithms to compute shortest paths, minimum cuts, and maximum flows. Our linear-time algorithm improves upon the decomposition algorithm used in the state-of-the-art algorithm for minimum $$st$$-cut (Italiano, Nussbaum, Sankowski, and Wulff-Nilsen, STOC 2011), removing one of the bottlenecks in the overall running time of their algorithm (analogously for minimum cut in planar and bounded-genus graphs).

@inproceedings{KMS13,
author    = {Philip N. Klein
and Shay Mozes
and Christian Sommer},
title     = {Structured Recursive Separator Decompositions
for Planar Graphs in Linear Time},
year      = {2013},
booktitle = {45th ACM Symposium on Theory of Computing (STOC)},
pages     = {505--514},
url       = {http://dx.doi.org/10.1145/2488608.2488672},
doi       = {10.1145/2488608.2488672},
}


Official version
Local version (322.0 KB)
arXiv

HomePublications → Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
{"ft_lang_label":"__label__en","ft_lang_prob":0.8640856,"math_prob":0.9970793,"size":1947,"snap":"2020-45-2020-50","text_gpt3_token_len":496,"char_repetition_ratio":0.11219763,"word_repetition_ratio":0.042857144,"special_character_ratio":0.27991784,"punctuation_ratio":0.12643678,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9984775,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-26T21:18:55Z\",\"WARC-Record-ID\":\"<urn:uuid:699e0530-764e-4824-ba6f-5e1189439499>\",\"Content-Length\":\"3491\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6514199b-e3ca-4318-8a62-4a20fae357e6>\",\"WARC-Concurrent-To\":\"<urn:uuid:c261ac0c-f01a-4afa-a503-2091cd4d67a2>\",\"WARC-IP-Address\":\"194.191.24.28\",\"WARC-Target-URI\":\"http://chsommer.com/rdiv.htm\",\"WARC-Payload-Digest\":\"sha1:437L53TX3VQBQG6FHREW6L2VFGN3W4LU\",\"WARC-Block-Digest\":\"sha1:I47C67SRVNGYFGDNPAZBDLHNE7NHBXAJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107892062.70_warc_CC-MAIN-20201026204531-20201026234531-00527.warc.gz\"}"}