# Layered Graphs: Applications and Algorithms
## 2 Layered Graph  
Consider a set of undirected graphs, \(G_{1},G_{2},\ldots,G_{q}\), on the corresponding vertex sets \((V_{1},V_{2},\ldots,V_{q})\) and the edge sets \((E_{1},E_{2},\ldots,E_{q}\) i.e., \(G_{i}=(V_{i},E_{i}))\). Consider a graph, \(G\), that is formed from \(\forall_{i}\ G_{i}\) with special additional edges called _inter-layer edges_, denoted as \(E_{ij}\), where \(j=i+1\) and \(E_{ij}\) denotes the edges between \(V_{i}\) and \(V_{j}\). We call such a graph a _layered graph_, denoted as \(LG\), where the \(i\)-th layer is \(G_{i}\). Note that for any given \(i\), \(E_{ij}\), where \(j=i+1\) can be \(\phi\) and \(\forall_{i\
eq i+1}E_{il}=\phi\). Every vertex within a given layer gets a label from \((1,2,3,\ldots,k)\). Thus, \(V_{i}\subseteq\{V_{1},V_{i2},\ldots,V_{ik}\}\). Note that \(V_{ix}\) is the vertex number, \(x\), in layer \(i\). However, in layer \(i\), the vertex number, \(x\), may not exist. Further, if \((V_{ix},V_{i+1}\,y)\in E_{i\,i+1}\), then it follows that vertex \(x\) is present in layer \(i\) and vertex \(y\) is present in layer \(i+1\). We defined the following restrictions on a layered graph. Several of the these restrictions can be combined. Please see Figure 1.  
* If \(\forall_{i}\ \mid V_{i}\mid\leq k\), then a _k-restricted layered graph_, i.e., \(LG_{k}\), is obtained. \(LG_{k}^{q}\) denotes an \(LG\) with \(q\) layers. \(LG_{k}^{n,q}\) denotes an \(LG_{k}^{q}\) with \(n\) vertices. * If \(\forall_{t}\ (V_{it},V_{jit})\) is an inter-layer edge \(\rightarrow(t=u)\wedge j\in\{i-1,i+1\}\), then a _linear layered graph_, i.e., \(LLG\), is obtained. \(LLG_{k}\) denotes an \(LLG\) that is _k-restricted_. * If \(\forall_{i}\ G_{i}\) is a connected component, then a _single component layered graph_, i.e., \(SLG\), is obtained. Figure 1: (a) \(LG_{6}^{24,4}\). (b) \(LL_{6}^{23,4}\). (c) \(SL_{6}^{24,4}\). (d) \(SLL_{6}^{24,4}\). Layer 1 is the topmost and layer 4 is the bottommost. Vertices have labels from \(\{1,2,3,4,5,6\}\) within a given layer. Intra-layer edge is a thick line whereas inter-layer edge is thinner. (a–d) are \(CLG\)s as well. (a,b) are not a \(SLG\)s ((a): layer 4 has two components {1,3,5} and {2,4,6}. (b): layer 4 has three components {1,6}, {2,5} and {4}; vertex 3 does not exist, only a placeholder is shown). * If \(G\) is required to be a connected component, then a _connected layered graph_, i.e., \(CLG\), is obtained. The problems of computing the adjacent swap distance between unsigned strings, adjacent swap distance between signed strings and short reversal distance were addressed in [1]. If the alphabet is \(\Sigma\), \(|\Sigma|\) is \(k\), the source string is \(\alpha\) and the destination string is \(\beta\) and the length of \(\alpha\) (and \(\beta\)) is \(n\), a _pairing diagram_ can be drawn for \(\alpha\) and \(\beta\), where all elements of \(\alpha\) and \(\beta\) are treated as vertices, and perfect matching is performed on all \(2n\) vertices, where each edge corresponds to \((\alpha[i],\,\beta[j])\) (here, both \(\alpha[i]\), \(\beta[j]\) denote the same symbol [1]). The solutions to the above problems are based on _optimum pairing_ (in contrast to any perfect matching), where there is an edge from the \(i\)-th occurrence of a symbol \(x\) in \(\alpha\) to the \(i\)-th occurrence of \(x\) in \(\beta\); the corresponding pairing diagram is the _optimum pairing diagram_. The solutions for adjacent swap distances are complete. However, the solution suggests that the short reversal distance is partial; it can solve very few sub-cases. Several distance problems on strings have been shown to be NP-complete [30]. However, the complexity of short reversal distance problem is unknown. The short reversal distance was studied in [2]. It was shown that the edges corresponding to two consecutive occurrences of a symbol \(x\) in optimum pairing form a special edge-pair if they meet certain criteria.