graph associated with a P node that has two or more virtual edges. In this case the components formed by the removal of u and v are represented by subtrees of the SPQR tree, one for each virtual edge in the node. The two vertices u and v may be two vertices in the graph associated with an S node such that either u and v are not adjacent, or the edge uv is virtual. If the edge is virtual, then the pair (u,v) also belongs to a node of type P and R and the components are as described above. If the two vertices are not adjacent then the two components are represented by two paths of the cycle graph associated with the S node and with the SPQR tree nodes attached to those two paths. Representing all embeddings of planar graphs If a planar graph is 3-connected, it has a unique planar embedding up to the choice of which face is the outer face and of orientation of the embedding: the faces of the embedding are exactly the nonseparating cycles of the graph. However, for a planar graph (with labeled vertices and edges) that is 2-connected but not 3-connected, there may be greater freedom in finding a planar embedding. Specifically, whenever two nodes in the SPQR tree of the graph are connected by a pair of virtual edges, it is possible to flip the orientation of one of the nodes (replacing it by its mirror image) relative to the other one. Additionally, in a P node of the SPQR tree, the different parts of the graph connected to virtual edges of the P node may be arbitrarily permuted. All planar representations may be described in this way. See also Block-cut tree, a similar tree structure for the 2-vertex-connected components Gomory–Hu tree, a different tree structure that characterizes the edge connectivity of a graph Tree decomposition, a generalization (no longer unique) to larger cuts Notes References . . . . . . . External links SPQR tree implementation in the Open Graph Drawing Framework. The tree of the triconnected components Java implementation in the jBPT library (see TCTree class). Trees (data structures) Graph connectivity Graph data structures