{"id":14802,"date":"2022-05-28T20:22:37","date_gmt":"2022-05-29T00:22:37","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14802"},"modified":"2026-06-09T10:44:07","modified_gmt":"2026-06-09T14:44:07","slug":"tr-176-edge-separators-of-planar-and-outerplanar-graphs-with-applications","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-176-edge-separators-of-planar-and-outerplanar-graphs-with-applications\/","title":{"rendered":"TR-176: Edge Separators of Planar and Outerplanar Graphs with Applications"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-176: Edge Separators of Planar and Outerplanar Graphs with Applications\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/\">Technical Report<\/a>&nbsp;<strong>TR-176<\/strong><br>May 1990<\/p>\n\n\n\n<h2 id=\"edge-separators-of-planar-and-outerplanar-graphs-with-applications\" class=\"wp-block-heading\">Edge Separators of Planar and Outerplanar Graphs with Applications<\/h2>\n\n\n\n<p>Krzystof Diks, Hristo N. Djidjev, Ondrej Sykora , Imrich Vrto<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>We consider the problem of finding a small set of edges whose removal divides a given graph into roughly equal parts. We show that every planar graph with nvertices and a maximal degree k has an O()-edge separator, which bound is asymptotically optimal. This improves the previously best known upper bound of 0(k In). We prove that the bisection width of the class of planar graphs and trees of n vertices and degree k is 0( and 0(k log nllog k) respectively, both optimal within a constant factor. All proofs are constructive and yield optimal O(n) algorithms. The separator theorems are applied to embed efficiently planar and outerplanar graphs into binary trees, hypercubes, butterfly graphs, CCC graphs, shuffle-exchange graphs, de Brujn graphs, and d-dimensional meshes. The embeddings are shown to be optimal or almost optimal with respect to the average dilation and the expansion of the embedding.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-176.pdf\">TR-176.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-176May 1990 Edge Separators of Planar and Outerplanar Graphs with Applications Krzystof Diks, Hristo N. Djidjev, Ondrej Sykora , Imrich Vrto Abstract We consider the problem of finding a small set of edges whose removal divides a given graph into roughly equal parts. We show that every planar graph with nvertices and a [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11906,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-14802","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14802","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14802"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14802\/revisions"}],"predecessor-version":[{"id":24537,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14802\/revisions\/24537"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11906"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14802"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14802"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}