Dividing a Graph into Triconnected Components

DOI10.1137/0202012zbMath0281.05111OpenAlexW1994556169WikidataQ29394586 ScholiaQ29394586MaRDI QIDQ4767335

John E. Hopcrofts, Robert Endre Tarjan

Publication date: 1973

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

Full work available at URL: https://hdl.handle.net/1813/6037

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Decomposition of 3-connected graphs, Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Fully dynamic 2-edge-connectivity in planar graphs, Parameterized Graph Cleaning Problems, Upward planarity testing, On the Hardness and Approximability of Planar Biconnectivity Augmentation, Computing orthogonal drawings with the minimum number of bends, A heuristic approach for dividing graphs into bi-connected components with a size constraint, A decomposition algorithm for network reliability evaluation, Drawing planar graphs using the canonical ordering, Generalized flowers in \(k\)-connected graphs, The structure of a decomposition of a triconnected graph, Jordan-like characterization of automorphism groups of planar graphs, Embedding graphs in the torus in linear time, On the bond polytope, Upward book embeddability of \(st\)-graphs: complexity and algorithms, Synchronized Planarity with Applications to Constrained Planarity Problems, Finding agreement cherry-reduced subnetworks in level-1 networks, Pathlength of outerplanar graphs, Rectilinear planarity of partial 2-trees, A more compact visibility representation, An annotated review on graph drawing and its applications, Computing Circuit Polynomials in the Algebraic Rigidity Matroid, Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time, Construction sequences and certifying 3-connectivity, A linear-time algorithm for star-shaped drawings of planar graphs with the minimum number of concave corners, Algorithmic and complexity aspects of problems related to total restrained domination for graphs, Almost exact matchings, On 2-strong connectivity orientations of mixed graphs and related problems, A linear delay algorithm for enumeration of 2-edge/vertex-connected induced subgraphs, On-line convex planarity testing, DFS tree construction: Algorithms and characterizations, Global rigidity of direction-length frameworks, Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\), Local convergence of random planar graphs, Maximum Cut Parameterized by Crossing Number, An SPQR-tree-like embedding representation for upward planarity, Graphs with no \(K_{3,3}\) minor containing a fixed edge, Unnamed Item, Unnamed Item, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Efficient algorithmic learning of the structure of permutation groups by examples, Orthogonal drawings of graphs for the automation of VLSI circuit design, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction, The source location problem with local 3-vertex-connectivity requirements, Finding densest \(k\)-connected subgraphs, Re-embedding a 1-plane graph for a straight-line drawing in linear time, VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY, Decremental SPQR-trees for Planar Graphs, Some Tractable Win-Lose Games, The use of tree transducers to compute translations between graph algebras, Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge, Polynomial-time Classification of Skew-symmetrizable Matrices with a Positive Definite Quasi-Cartan Companion, The exact overall time distribution of a project with uncertain task durations, Decomposition plans for geometric constraint systems. I: Performance measures for CAD, A tighter insertion-based approximation of the crossing number, Acyclically pushable bipartite permutation digraphs: an algorithm, A structure theorem for graphs with no cycle with a unique chord and its consequences, Unnamed Item, Fast incremental planarity testing, Maintenance of triconnected components of graphs, Graph isomorphism restricted by lists, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Advances in the Planarization Method: Effective Multiple Edge Insertions, Unnamed Item, On the Complexity of Matroid Isomorphism Problems, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, Unnamed Item, Kernelization of Whitney Switches, The non-solvability by radicals of generic 3-connected planar Laman graphs, Kernelization of Whitney Switches, Tractable minor-free generalization of planar zero-field Ising models, Percolation thresholds for robust network connectivity, Blocks in \(k\)-connected graphs, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Linear time algorithms for graph search and connectivity determination on complement graphs., An improved algorithm for decomposing arc flows into multipath flows, Nonseparating Cocircuits in Binary Matroids, Finding all minimum-size separating vertex sets in a graph, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs, Safe separators for treewidth, Data structures for two-edge connectivity in planar graphs, A linear algorithm for embedding planar graphs using PQ-trees, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, A decomposition algorithm for multi-terminal network flows, On the equivalence of constrained and unconstrained flows, Path-based depth-first search for strong and biconnected components, Planarity testing in parallel, Binary constraint satisfaction problems defined by excluded topological minors, The arborescence-realization problem, \(\Delta \)-list vertex coloring in linear time, Using SPQR-trees to speed up algorithms based on 2-cutset decompositions, The input/output complexity of transitive closure, Network security and contagion, A topological approach to dynamic graph connectivity, Acyclic k-connected subgraphs for distributed alternate routing in communications networks, Linear-time recognition of map graphs with outerplanar witness, 3-connected reduction for regular graph covers, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Edge-packing planar graphs by cyclic graphs, Projective plan and Möbius band obstructions, Separator-based data reduction for signed graph balancing, A plane graph representation of triconnected graphs, Balanced group-labeled graphs, On the secure domination numbers of maximal outerplanar graphs, Good spanning trees in graph drawing, Counting labelled three-connected and homeomorphically irreducible two- connected graphs, Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs, The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\), Coloring algorithms for \(K_ 5\)-minor free graphs, Connectivity of plane triangulations, On the complexity of matroid isomorphism problem, Minimum cost star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints, On graphs with no induced subdivision of \(K_4\), Subgraphs of 4-regular planar graphs, Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra, Graph connectivity, partial words, and a theorem of Fine and Wilf, Enumerating the cycles of a digraph: a new preprocessing strategy, A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing, Testing planar pictures for isomorphism in linear time, Trémaux trees and planarity, A linear-time algorithm for testing outer-1-planarity, A linear-time algorithm for finding an ambitus, Guthrie's problem: new equivalences and rapid reductions, Characterizing and recognizing 4-map graphs, A new graph triconnectivity algorithm and its parallelization, Certifying 3-edge-connectivity, Deciding whether graph \(G\) has page number one is in NC, An extension of the multi-path algorithm for finding Hamilton cycles, Detecting cycles through three fixed vertices in a graph, Recognising \(k\)-connected hypergraphs in cubic time, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, The decomposition of graphs into \(k\)-connected components, A linear time algorithm for computing 3-edge-connected components in a multigraph, The anti-join composition and polyhedra, Locating facilities which interact: Some solvable cases, Parallel search algorithms for graphs and trees, Parameterized graph cleaning problems, A minimum 3-connectivity augmentation of a graph, A linear algorithm for the all-bidirectional-edges problem on planar graphs, Globally rigid circuits of the direction-length rigidity matroid, Finding large cycles in Hamiltonian graphs, Crossing number and weighted crossing number of near-planar graphs, Rigidity, global rigidity, and graph decomposition, On the complexity of embedding planar graphs to minimize certain distance measures, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, Generating 3-vertex connected spanning subgraphs, Graph isomorphism, general remarks, Non-planar core reduction of graphs, Testing planarity of geometric automorphisms in linear time, Faster approximation algorithms for weighted triconnectivity augmentation problems, A smallest augmentation to 3-connect a graph, Structure and enumeration of two-connected graphs with prescribed three-connected components, Canonical decompositions of symmetric submodular systems, Connectivity of workflow nets: The foundations of stepwise verification, On testing consecutive-ones property in parallel, Advances in the theory and practice of graph drawing, An algorithm for constructing star-shaped drawings of plane graphs, Rigid tensegrity labelings of graphs, A linear algorithm for the domination number of a series-parallel graph, On the NP-hardness of edge-deletion and -contraction problems, Balanced cycles and holes in bipartite graphs, A note on finding the bridges of a graph, Edge-contraction problems, Sewing ribbons on graphs in space, Graph isomorphism problem, Drawing plane graphs nicely, Incremental convex planarity testing, Uncovering generalized-network structure in matrices, Generation of trees of a graph with the use of decomposition, Decomposition by clique separators, Depth-first search is inherently sequential, An approach to the subgraph homeomorphism problem, Representing polyhedra: Faces are better than vertices, Relational depth-first-search with applications, Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation, Improved algorithms for graph four-connectivity, 4-edge-coloring graphs of maximum degree 3 in linear time, Enumeration of articulation pairs of a planar graph, Independent trees in graphs