# Layered Graphs: Applications and Algorithms
## 1 Introduction
Several articles improved the complexity of the exponential algorithms that compute an MIS on a general graph [15; 16]. [PERSON] and [PERSON] showed that MIS is polynomially solvable for the class of \(S_{1,2,k}\)-free planar graphs, generalizing several previously known results, where \(S_{1,2,k}\) is the graph consisting of three induced paths of lengths \(1,2\) and \(k\) with a common initial vertex [17]. The minimum vertex cover problem on \(G\) seeks to identify a vertex cover with minimum cardinality, i.e., minimum vertex cover or MVC. If \(V^{*}\subseteq V\) is the MVC of \(G\), then \(\forall e=(u,v)\in E\), \(u\in V^{*}\vee v\in V^{*}\). In this article, \(G\) is undirected, so an edge \((u,v)\) is understood to be an undirected edge. The minimum dominating set (i.e., MDS) and the minimum connected dominating set (i.e., MCD) problems seek to identify a dominating set i.e., DS and a connected dominating set i.e., CDS, respectively, with minimum cardinalities. The MVC, MDS and MCD problems on general graphs are known to be NP-complete [6]. [PERSON] and [PERSON] showed that MVC is one of the first NP-complete problems [6]. In connected vertex cover problems (i.e., MCV), given a connected graph (G), a connected vertex cover (i.e., CVC) with minimum cardinality is sought. [PERSON] and [PERSON] proved that MCV is NP-complete [18]. For trees and bipartite graphs, the minimum vertex cover can be identified in polynomial time [19; 20]. [PERSON] and [PERSON] proved that the MCV problem is NP-hard in planar graphs, with a maximum degree of 4 [6]. [PERSON] et al. proved that for 4-regular graphs, the MCV problem is NP-hard [21]. It has been shown that for series-parallel graphs, which are a set of planar graphs, the minimum vertex cover can be computed in linear time [22]. [PERSON] and [PERSON] showed that the MDS problems on planar graphs with maximum vertex degree 3 and planar graphs that are regular with degree 4 are NP-complete [6]. MCD is NP-complete even for planar graphs that are regular with degree 4 [6]. [PERSON] showed that the problem of identifying a MDS is NP-complete for split graphs and bipartite graphs [23]. [PERSON] et al. proved that MDS in trees can be computed in linear time [24]. [PERSON] designed various approximation algorithms for planar graphs [25]. [PERSON] and [PERSON] showed that MDS and MCD are NP-complete for chordal bipartite graphs [26]. [PERSON] et al. proved that for a given circular arc graph with \(n\) sorted arcs, MCD is linear in time and space [27]. [PERSON] et al. proposed an algorithm with a time complexity faster than \(2^{n}\) to solve the connected dominating set problem [28]. The term \"layered graph\" has been used in the literature. The hop-constrained minimum spanning tree problem related to the design of centralized telecommunication networks with quality of service (QoS) constraints is NP-hard [29]. A graph known as a _layered graph_ was constructed from a given input graph, and the authors showed that the hop-constrained minimum spanning tree problem is equivalent to the Steiner tree problem. In software architecture, the system is divided into several layers; this has been viewed as a graph with several layers. In this article, we define a new class of graphs that we call _layered graphs_ and design algorithms for various graph-theoretic problems.