Partitioning Planar Graphs

DOI10.1137/0221016MaRDI QIDQ3990649zbMATH OpenOpenAlexFDO

Authors Thang Nguyen Bui, Andrew Peck

Publication date 28 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0221016

zbMATH Keywords

graph partitioningplanar graphsouterplanar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Path partitions of planar graphs
• Graph partitioning
• scientific article; zbMATH DE number 637295
• scientific article; zbMATH DE number 1926663
• Partitioning planar graphs with costs and weights
• Partitions of Graphs
• scientific article; zbMATH DE number 4068928
• Note on partitions of planar graphs
• Outerplanar partitions of planar graphs
• scientific article; zbMATH DE number 3867385

Cited in

(29)

• Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
• scientific article; zbMATH DE number 1262793 (Why is no real title available?)
• A plane graph representation of triconnected graphs
• scientific article; zbMATH DE number 7525479 (Why is no real title available?)
• Planarizing graphs and their drawings by vertex splitting
• Finding good approximate vertex and edge partitions is NP-hard
• Parallel approximation schemes for problems on planar graphs
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• scientific article; zbMATH DE number 4101213 (Why is no real title available?)
• scientific article; zbMATH DE number 4101215 (Why is no real title available?)
• scientific article; zbMATH DE number 4091555 (Why is no real title available?)
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
• scientific article; zbMATH DE number 3924818 (Why is no real title available?)
• Finding the closed partition of a planar graph
• Subdivisions in planar graphs
• Bisection of bounded treewidth graphs by convolutions
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• On the parameterized complexity of computing balanced partitions in graphs
• scientific article; zbMATH DE number 4108779 (Why is no real title available?)
• On alliance partitions and bisection width for planar graphs
• scientific article; zbMATH DE number 975383 (Why is no real title available?)
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Generating irregular partitionable data structures
• Minimum Bisection Is Fixed-Parameter Tractable
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

This page was built for publication: Partitioning Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990649)