An Alternative Proof for the NP-completeness of Top Right Access point-Minimum Length Corridor Problem

In the Top Right Access point Minimum Length Corridor (TRA-MLC) problem [1], a rectangular boundary partitioned into rectilinear polygons is given and the problem is to find a corridor of least total length and it must include the top right corner of the outer rectangular boundary. A corridor is a tree containing a set of line segments lying along the outer rectangular boundary and/or on the boundary of the rectilinear polygons. The corridor must contain at least one point from the boundaries of the outer rectangle and also the rectilinear polygons. Gutierrez and Gonzalez [1] proved that the MLC problem, along with some of its restricted versions and variants, are NP-complete. In this paper, we give a shorter proof of NP-Completeness of TRA-MLC by findig the reduction in the following way.

• Priyadarsini P.L.K
• Hemalatha T.

• NP-complete
• 2-connected planar graph
• Grid embedding of a plane graph.

[1] A.Gonzalez-Gutierrez and T.F.Gonzalez , " Complexity of the Minimum-Length Corridor Problem ",J. Comp. Geometry, Theory and Applns.,Els. vol.37, no.2, 2007, 72-103.
[2] E.D.Domaine and J.O.Rourke, " Open Problems from CCCG 2000
", Proc. of the 13th Canadian Conference on Computational Geometry(
CCCG 2001), 2001, 185-187.
[3] D.Eppstein , " Some Open Problems in Graph Theory and Computational
Geometry ", 2001 http:// www.ics.uci.edu/˜ eppstein/200-f01.pdf.
[4] M.R.Garey and D.S.Johnson , " The Rectilinear Steiner Tree Problem is
NP - complete ", J. Appl. Math.(SIAM), vol. 32, no. 4, 1977, pp. 826-834.
[5] Priyadarsini P.L.K and Hemalatha T, " Connected Vertex Cover in 2-
Connected Planar Graph with Maximum Degree 4 is NP-complete ",
submitted to International conference AMNA 2007.
[6] M.R. Garey and D.S. Johnson , Computers and Intractability: A Guide
to the Theory of NP-Completeness, W.H. Freeman & Co, 1979.
[7] C.H. Papadimitriou and K. Steiglitz , Combinatorial optimization: Algorithms
and Complexity, Prentice Hall India, 1997.
[8] R. Weiskircher, " Drawing Planar Graphs ", in " Drawing Graphs" (
M.Kaufmann & D.Wagner, Eds.), pp. 23-45, LNCS 2025,Springer-Verlag,
2001.
[9] R.Tamassia and I.G.Tollis, "A Unified Aproach to Visibility Representation
of Planar Graphs",J. Discrete and Computational Geometry,
Springer-Verlag, vol. 1, 1986, 321-341.
[10] R.Tamassia and I.G.Tollis, "Planar Grid Embedding in Linear Time",
IEEE Transactions on circuits and systems, vol. 36 no. 9, 1989, 1230-
1234.