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

Authors: Priyadarsini P.L.K, Hemalatha T.

Abstract:

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.

Keywords: NP-complete, 2-connected planar graph, Grid embedding of a plane graph.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332834

References:

[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.