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

DOI10.1016/S0020-0190(97)00083-5MaRDI QIDQ287104zbMATH OpenOpenAlexWikidataFDO

Authors Shin-Ichi Nakano, Md. Saidur Rahman, Takao Nishizeki

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

\(st\)-numberingcanonical decompositionfour-connected planar graphgraph partitionlinear-time algorithms

Mathematics Subject Classification ID

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

Recommendations

• A linear algorithm for resource four-partitioning four-connected planar graphs
• scientific article; zbMATH DE number 1262807
• A linear-time algorithm to find four independent spanning trees in four connected planar graphs
• A linear time algorithm for graph partition problems
• Planar graph bipartization in linear time
• scientific article; zbMATH DE number 7740902
• Determining 4-Edge-Connected Components in Linear Time
• scientific article; zbMATH DE number 4195169
• On triangulating planar graphs under the four-connectivity constraint

Cites work

• A homology theory for spanning tress of a graph
• A linear algorithm for bipartition of biconnected graphs
• An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• On the complexity of partitioning graphs into connected subgraphs

Cited in

(24)

• On the shape of decomposable trees
• Path partitioning planar graphs of girth 4 without adjacent short cycles
• Edge-orders
• A linear algorithm for resource four-partitioning four-connected planar graphs
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• NP-completeness of st-orientations for plane graphs
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• scientific article; zbMATH DE number 4195169 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1262808 (Why is no real title available?)
• On minimal arbitrarily partitionable graphs
• A linear-time algorithm to find four independent spanning trees in four connected planar graphs
• PARTITIONING TREES OF SUPPLY AND DEMAND
• CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS
• scientific article; zbMATH DE number 2230227 (Why is no real title available?)
• scientific article; zbMATH DE number 7740902 (Why is no real title available?)
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• Connected partitions via connected dominating sets
• Algorithms for computing a parameterized \(st\)-orientation
• Decomposing trees with large diameter

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

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