Series-parallel graph

Last updated
Series and parallel composition operations for series-parallel graphs. Series parallel composition.svg
Series and parallel composition operations for series-parallel graphs.

In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.

Contents

Definition and terminology

In this context, the term graph means multigraph.

There are several ways to define series-parallel graphs. The following definition basically follows the one used by David Eppstein. [1]

A two-terminal graph (TTG) is a graph with two distinguished vertices, s and t called source and sink, respectively.

The parallel compositionPc = Pc(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sources of X and Y to create the source of Pc and merging the sinks of X and Y to create the sink of Pc.

The series compositionSc = Sc(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sink of X with the source of Y. The source of X becomes the source of Sc and the sink of Y becomes the sink of Sc.

A two-terminal series-parallel graph (TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph K 2 with assigned terminals.

Definition 1. Finally, a graph is called series-parallel (SP-graph), if it is a TTSPG when some two of its vertices are regarded as source and sink.

In a similar way one may define series-parallel digraphs, constructed from copies of single-arc graphs, with arcs directed from the source to the sink.

Alternative definition

The following definition specifies the same class of graphs. [2]

Definition 2. A graph is an SP-graph, if it may be turned into K 2 by a sequence of the following operations:

Properties

Every series-parallel graph has treewidth at most 2 and branchwidth at most 2. [3] Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every biconnected component is a series-parallel graph. [4] [5] The maximal series-parallel graphs, graphs to which no additional edges can be added without destroying their series-parallel structure, are exactly the 2-trees.

2-connected series-parallel graphs are characterised by having no subgraph homeomorphic to K4. [3]

Series parallel graphs may also be characterized by their ear decompositions. [1]

Computational complexity

SP-graphs may be recognized in linear time [6] and their series-parallel decomposition may be constructed in linear time as well.

Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard graph problems are solvable in linear time on SP-graphs, [7] including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion. Some of these problems are NP-complete for general graphs. The solution capitalizes on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions.

Generalization

The generalized series-parallel graphs (GSP-graphs) are an extension of the SP-graphs [8] with the same algorithmic efficiency for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and outerplanar graphs.

GSP graphs may be specified by Definition 2 augmented with the third operation of deletion of a dangling vertex (vertex of degree 1). Alternatively, Definition 1 may be augmented with the following operation.

An SPQR tree is a tree structure that can be defined for an arbitrary 2-vertex-connected graph. It has S-nodes, which are analogous to the series composition operations in series-parallel graphs, P-nodes, which are analogous to the parallel composition operations in series-parallel graphs, and R-nodes, which do not correspond to series-parallel composition operations. A 2-connected graph is series-parallel if and only if there are no R-nodes in its SPQR tree.

See also

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.

Tree decomposition mapping of a graph into a tree

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

Graph (discrete mathematics) Mathematical structure consisting of vertices and edges connecting some pairs of vertices

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Maximum flow problem

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

Cograph a type of graph, formed recursively by complementation and disjoint union operations

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In graph theory, the treewidth of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: the size of the largest vertex set in a tree decomposition of the graph, the size of the largest clique in a chordal completion of the graph, the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit-evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.

Graph operations produce new graphs from initial ones. They may be separated into the following major categories.

SPQR tree concept in graph theory, a branch of mathematics

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

Branch-decomposition term in graph theory

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

Clique-sum term in graph theory

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have at most k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.

Halin graph a type of planar graph formed from a tree by adding a cycle of edges through its leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

Directed graph Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

Series-parallel partial order

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.

References

  1. 1 2 Eppstein, David (1992). "Parallel recognition of series-parallel graphs" (PDF). Information and Computation . 98 (1): 41–55. doi:10.1016/0890-5401(92)90041-D.
  2. Duffin, R. J. (1965). "Topology of Series-Parallel Networks". Journal of Mathematical Analysis and Applications. 10 (2): 303–313. doi:10.1016/0022-247X(65)90125-3.
  3. 1 2 Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph classes: a survey. SIAM Monographs on Discrete Mathematics. and Applications. 3. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp.  172–174. ISBN   978-0-898714-32-6. Zbl   0919.05001.
  4. Bodlaender, H. (1998). "A partial k-arboretum of graphs with bounded treewidth". Theoretical Computer Science . 209 (1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4. hdl: 1874/18312 .
  5. Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three". Journal of Combinatorial Theory, Series B . 86 (1): 148–171. doi:10.1006/jctb.2002.2120.
  6. Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982). "The recognition of series parallel digraphs". SIAM Journal on Computing . 11 (2): 289–313. doi:10.1137/0211023.
  7. Takamizawa, K.; Nishizeki, T.; Saito, N. (1982). "Linear-time computability of combinatorial problems on series-parallel graphs". Journal of the ACM . 29 (3): 623–641. doi:10.1145/322326.322328. S2CID   16082154.
  8. Korneyenko, N. M. (1994). "Combinatorial algorithms on a class of graphs". Discrete Applied Mathematics . 54 (2–3): 215–217. doi:10.1016/0166-218X(94)90022-1. Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109–111 (in Russian)