linear-time construction of floor plans for plane triangulations

This paper focuses on a novel approach for producing a floor plan (fp), either a rectangular (rfp) or an orthogonal (ofp) based on the concept of orthogo nal drawings, which satisfies the adjacency relations given by any bi-connected plane triangulation g. previous algorithms for constructing a fp are primarily restricted to the cases given below: (i) a bi-connected plane triangulation without separating triangles (sts) and with at most 4 corner implying paths (cips), known as properly triangulated planar graph (ptpg). (ii) a bi-connected plane triangulation with an exterior face of length 3 and no cips, known as maximal planar graph (mpg). the fp obtained in the above two cases is a rfp or an ofp respectively. in this paper, we present the construction of a fp (rfp if exists, else an ofp), for a bi-connected plane triangulation g in linear-time.