%0 Journal Article
	%A Priyadarsini P. L. K and  Hemalatha T.
	%D 2007
	%J International Journal of Mathematical and Computational Sciences
	%B World Academy of Science, Engineering and Technology
	%I Open Science Index 11, 2007
	%T Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete
	%U https://publications.waset.org/pdf/13006
	%V 11
	%X This paper proves that the problem of finding connected
vertex cover in a 2-connected planar graph ( CVC-2 ) with maximum degree 4 is NP-complete. The motivation for proving this result is to
give a shorter and simpler proof of NP-Completeness of TRA-MLC (the Top Right Access point Minimum-Length Corridor) problem [1], by finding the reduction from CVC-2. TRA-MLC has many applications in laying optical fibre cables for data communication and electrical wiring in floor plans.The problem of finding connected vertex cover in any planar graph ( CVC ) with maximum degree 4 is NP-complete [2]. We first show that CVC-2 belongs to NP and then we find a polynomial reduction from CVC to CVC-2. Let a graph G0 and an integer K form an instance of CVC, where G0 is a planar graph and K is an upper bound on the size of the connected vertex cover in G0. We construct a 2-connected planar graph, say G, by identifying the blocks and cut vertices of G0, and then finding the planar representation of all the blocks of G0, leading to a plane graph G1. We replace the cut vertices with cycles in such a way that the resultant graph G is a 2-connected planar graph with maximum
degree 4. We consider L = K -2t+3 t i=1 di where t is the number of cut vertices in G1 and di is the number of blocks for which ith cut vertex is common. We prove that G will have a connected vertex
cover with size less than or equal to L if and only if G0 has a connected vertex cover of size less than or equal to K.
	%P 570 - 573