On-line maintenance of triconnected components with SPQR-trees
From MaRDI portal
Publication:1911463
zbMath0843.68088MaRDI QIDQ1911463
Giuseppe Di Battista, Roberto Tamassia
Publication date: 6 June 1996
Published in: Algorithmica (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68M99)
Related Items (49)
Linear-time recognition of map graphs with outerplanar witness ⋮ Computing orthogonal drawings with the minimum number of bends ⋮ Orthogonal Graph Drawing with Inflexible Edges ⋮ Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario ⋮ Maintaining triconnected components under node expansion ⋮ Synchronized Planarity with Applications to Constrained Planarity Problems ⋮ Unit-length rectangular drawings of graphs ⋮ A new perspective on clustered planarity as a combinatorial embedding problem ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Simultaneous Orthogonal Planarity ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ On-line convex planarity testing ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ Unnamed Item ⋮ Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph ⋮ Unnamed Item ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra ⋮ Multi-interval Pairwise Compatibility Graphs ⋮ Orthogonal graph drawing with flexibility constraints ⋮ Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree ⋮ A linear-time algorithm for testing outer-1-planarity ⋮ Characterizing and recognizing 4-map graphs ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Orthogonal graph drawing with inflexible edges ⋮ A branch-and-cut approach to the crossing number problem ⋮ Simpler algorithms for testing two-page book embedding of partitioned graphs ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ Relaxing the constraints of clustered planarity ⋮ Efficient authenticated data structures for graph connectivity and geometric search problems ⋮ Hierarchical partial planarity ⋮ Planar bus graphs ⋮ Unavoidable minors for graphs with large \(\ell_p\)-dimension ⋮ Optimization and Recognition for K 5-minor Free Graphs in Linear Time ⋮ Non-planar core reduction of graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Unnamed Item ⋮ TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY ⋮ CONVEX DRAWINGS OF PLANE GRAPHS OF MINIMUM OUTER APICES ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ Algorithms for 1-Planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Simultaneous Embedding ⋮ Maximum cycle packing using SPR-trees ⋮ Incremental convex planarity testing ⋮ Straight-line monotone grid drawings of series–parallel graphs ⋮ Monotone drawings of graphs with fixed embedding ⋮ Disconnectivity and relative positions in simultaneous embeddings
This page was built for publication: On-line maintenance of triconnected components with SPQR-trees
