A separator theorem for nonplanar graphs

1990/01/01 by Noga Alon, Paul Seymour, Robin Thomas · 14 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Cooperative Communication and Network Coding #Algorithm #Annotation #Computer science #Artificial intelligence #Database

paper · doi:10.1090/s0894-0347-1990-1065053-0

openalex publication_date 1990/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertex graph with no minor isomorphic to an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h"> <mml:semantics> <mml:mi>h</mml:mi> <mml:annotation encoding="application/x-tex">h</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertex complete graph. We prove that the vertices of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be partitioned into three sets <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A comma upper B comma upper C"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mspace width="thickmathspace"/> <mml:mi>B</mml:mi> <mml:mo>,</mml:mo> <mml:mspace width="thickmathspace"/> <mml:mi>C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">A, B, C</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that no edge joins a vertex in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with a vertex in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B"> <mml:semantics> <mml:mi>B</mml:mi> <mml:annotation encoding="application/x-tex">B</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , neither <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> nor <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B"> <mml:semantics> <mml:mi>B</mml:mi> <mml:annotation encoding="application/x-tex">B</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains more than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 n slash 3"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">2n/3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C"> <mml:semantics> <mml:mi>C</mml:mi> <mml:annotation encoding="application/x-tex">C</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains no more than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h Superscript 3 slash 2 Baseline n Superscript 1 slash 2"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">h^3/2n^1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper A comma upper B comma upper C right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mspace width="thickmathspace"/> <mml:mi>B</mml:mi> <mml:mo>,</mml:mo> <mml:mspace width="thickmathspace"/> <mml:mi>C</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(A, B, C)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in time <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis h Superscript 1 slash 2 Baseline n Superscript 1 slash 2 Baseline m right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class

Cited by

• Improved approximation algorithms for minimum-weight vertex separators
• A Separator-based Algorithm for the Graph Edit Distance Problem
• Separator-Based Graph Embedding into Multidimensional Grids with Small Edge-Congestion
• The first order definability of graphs with separators via the Ehrenfeucht game
• A Separator Theorem for String Graphs and its Applications
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Faster Shortest-Path Algorithms for Planar Graphs
• New upper bounds on the decomposability of planar graphs
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Graph separators: a parameterized view
• A Separator Theorem in Minor-Closed Classes
• Faster shortest-path algorithms for planar graphs
• Haven (graph theory) [wikipedia]
• Planar separator theorem [wikipedia]