Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 8 4 2023 12 31 Linear-time construction of floor plans for plane triangulations 673 692 14427 10.22049/cco.2022.27814.1361 EN Pinki Pinki Bits Pilani, Rajasthan Krishnendra Shekhawat Department of Mathematics, BITS Pilani, Pilani Campus, Rajasthan - 333031 Journal Article 2022 05 17 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 orthogonal drawings, which satisfies the adjacency relations given by any bi-connected plane triangulation $G$.<br />     Previous algorithms for constructing a FP are primarily restricted to the cases given below:<br />     \begin{enumerate}[(i)]<br />         \item 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).<br />         \item A bi-connected plane triangulation with an exterior face of length 3 and no CIPs, known as maximal planar graph (MPG).<br />     \end{enumerate}<br />     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. https://comb-opt.azaruniv.ac.ir/article_14427_f48cecc39d5cde003158900a75a3e6c7.pdf