{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T03:15:57Z","timestamp":1672542957110},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","funder":[{"name":"National Science and Engineering Research Council, Canada","award":["227693-2010"],"award-info":[{"award-number":["227693-2010"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> A graph [Formula: see text] is said to be triangulated if it has no chordless cycles of length 4 or more. Such a graph is said to be rigid if, for a valid assignment of edge lengths, it has a unique linear layout and non-rigid otherwise. Damaschke [Point placement on the line by distance data, Discrete Appl. Math. 127(1) (2003) 53\u201362] showed how to compute all linear layouts of a triangulated graph, for a valid assignment of lengths to the edges of [Formula: see text]. In this paper, we extend this result to weakly triangulated graphs, resolving an open problem. A weakly triangulated graph can be constructively characterized by a peripheral ordering of its edges. The main contribution of this paper is to exploit such an edge order to identify the rigid and non-rigid components of [Formula: see text]. We first show that a weakly triangulated graph without articulation points has at most [Formula: see text] different linear layouts, where [Formula: see text] is the number of quadrilaterals (4-cycles) in [Formula: see text]. When [Formula: see text] has articulation points, the number of linear layouts is at most [Formula: see text], where [Formula: see text] is the number of nodes in the block tree of [Formula: see text] and [Formula: see text] is the total number of quadrilaterals over all the blocks. Finally, we propose an algorithm for computing a peripheral edge order of [Formula: see text] by exploiting an interesting connection between this problem and the problem of identifying a two-pair in [Formula: see text]. Using an [Formula: see text] time solution for the latter problem, we propose an [Formula: see text] time algorithm for computing its peripheral edge order, where [Formula: see text] and [Formula: see text] are respectively the number of edges and vertices of [Formula: see text]. For sparse graphs, the time complexity can be improved to [Formula: see text], using the concept of handles [R. B. Hayward, J. P. Spinrad and R. Sritharan, Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3(2) (2007) 19pp]. <\/jats:p>","DOI":"10.1142\/s1793830916500385","type":"journal-article","created":{"date-parts":[[2016,4,5]],"date-time":"2016-04-05T04:38:42Z","timestamp":1459831122000},"page":"1650038","source":"Crossref","is-referenced-by-count":2,"title":["Linear layouts of weakly triangulated graphs"],"prefix":"10.1142","volume":"08","author":[{"given":"Asish","family":"Mukhopadhyay","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Windsor, Windsor, Ontario, N9B 3P4 Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. V.","family":"Rao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology, Guwahati 781 039, Assam, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sidharth","family":"Pardeshi","sequence":"additional","affiliation":[{"name":"Google Inc. 1600 Amphitheater Pkwy, Mountain View 94043, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivas","family":"Gundlapalli","sequence":"additional","affiliation":[{"name":"Oracle India Pvt. Limited, Hyderabad, Telengana, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,8]]},"reference":[{"key":"S1793830916500385BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90033-S"},{"key":"S1793830916500385BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"S1793830916500385BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00284-6"},{"key":"S1793830916500385BIB006","volume-title":"Graph Theory","author":"Diestel R.","year":"2005"},{"key":"S1793830916500385BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00083-X"},{"key":"S1793830916500385BIB009","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199601)21:1<67::AID-JGT9>3.0.CO;2-K"},{"key":"S1793830916500385BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240237"},{"key":"S1793830916500385BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/BF02287916"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830916500385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:43:55Z","timestamp":1565113435000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830916500385"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8]]},"references-count":8,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2016,8]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S1793830916500385"],"URL":"https:\/\/doi.org\/10.1142\/s1793830916500385","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8]]}}}