A linear-time algorithm for four-partitioning four-connected planar graphs

DOI10.1016/S0020-0190(97)00083-5zbMath1336.05136OpenAlexW1983999399WikidataQ60608631 ScholiaQ60608631MaRDI QIDQ287104

Shin-ichi Nakano, Takao Nishizeki, Md. Saidur Rahman

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00083-5

zbMATH Keywords

canonical decompositionlinear-time algorithms\(st\)-numberingfour-connected planar graphgraph partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (17)

FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS ⋮ On some properties of doughnut graphs ⋮ Max-min weight balanced connected partition ⋮ Partitioning powers of traceable or Hamiltonian graphs ⋮ A plane graph representation of triconnected graphs ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ On minimal arbitrarily partitionable graphs ⋮ Edge-orders ⋮ Algorithms for computing a parameterized \(st\)-orientation ⋮ NP-completeness of st-orientations for plane graphs ⋮ Decomposing trees with large diameter ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ PARTITIONING TREES OF SUPPLY AND DEMAND ⋮ Unnamed Item ⋮ CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS ⋮ On the shape of decomposable trees ⋮ A LINEAR-TIME ALGORITHM TO FIND FOUR INDEPENDENT SPANNING TREES IN FOUR CONNECTED PLANAR GRAPHS

Cites Work

• A linear algorithm for bipartition of biconnected graphs
• On the complexity of partitioning graphs into connected subgraphs
• An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
• A homology theory for spanning tress of a graph
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear-time algorithm for four-partitioning four-connected planar graphs