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

graph partitioncanonical decomposition\(st\)-numberingfour-connected planar graphlinear-time algorithms

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) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• 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
• On the complexity of partitioning graphs into connected subgraphs

Cited in

(22)

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

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)