{"entities":{"Q2479473":{"pageid":2490216,"ns":120,"title":"Item:Q2479473","lastrevid":73336878,"modified":"2026-04-14T15:29:11Z","type":"item","id":"Q2479473","labels":{"en":{"language":"en","value":"Efficient algorithms for the \\(d\\)-dimensional rigidity matroid of sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5254191"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$C5767006-FBE8-41C6-8D25-A9ED840803BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe73097196dcf04d08acb9ef6c0ac6b5efa13a5c","datavalue":{"value":{"text":"Efficient algorithms for the \\(d\\)-dimensional rigidity matroid of sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2479473$1EACFCEF-96E9-44E4-97E8-34EE1FA7C995","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"710942feb3eda65004de307abf51a07c588c2823","datavalue":{"value":"1149.05011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479473$508302EA-0A8F-4C1C-B6F0-4403790BA52C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"85700c8280a09d2d42c50671133166f6cce8694d","datavalue":{"value":{"entity-type":"item","numeric-id":243603,"id":"Q243603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$11760762-5A92-4488-B2B5-AE82A891B9D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$055DF3C3-53C1-4511-87E3-1BAB90F95F44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5e0cdb440ca46d9b8c69635fc01191f2bcf2170","datavalue":{"value":{"time":"+2008-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2479473$ABA1DD44-9B03-4A3C-A8D3-A46317616BA2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c8d977e4eb51e82141927b8ce7eed57bfed255a","datavalue":{"value":"Let \\(G\\) be a graph with maximum degree at most \\(d + 2\\) and minimum degree at most \\(d + 1\\), and consider the \\(d\\)-dimensional generic rigidity matroid of \\(G\\). By a recent result of \\textit{B. Jackson} and \\textit{T. Jord\u00e1n} in [J. Comb. Theory, Ser. B 95, No. 1, 118--133 (2005; Zbl 1070.05022)] the dependent sets of the generic \\(d\\)-dimensional rigidity matroid of such sparse graphs are exactly those that violate Laman's condition, and are therefore of limited size, bounded by \\(\\frac{(d - 1)(d+2)}{(d -2)}\\) for \\(d \\geq 3\\). This fact is used to obtain an algorithm, linear in \\(n\\), to detect independence of the edge set of \\(G\\). Moreover, if \\(G\\) is generically isostatic an algorithm is given, also linear in \\(n\\), to construct a Henneberg sequence for \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479473$E74147E5-AEB5-43DD-979C-904BAD10BCB4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479473$7ADC2A91-8015-4E82-A21F-D162503378DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15b1d7bde9e76f330399b339419e21095feaec37","datavalue":{"value":"5254191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479473$5C7D798D-284B-45D7-9989-1C87DD9492EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fc9b4be710777f73cfecbf4c32a017f7a37d717","datavalue":{"value":"rigid frameworks","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479473$BD7CE515-4BFA-4709-A577-8BE6E15379AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d5f441c0499e50b3f454817960ca1832b3e7722","datavalue":{"value":"generically rigid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479473$90A54B4A-9FF7-4197-A3BB-E0DBD1DD5B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15dfcf21b91b9690cabcdd4b49489f4b80fdffe6","datavalue":{"value":"generic rigidity matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479473$D7A0E1D2-E63D-4FD5-B9AC-64FD6FD5D4A1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99aa050a3c44bfaf6f196d26904cc4c97e1c205f","datavalue":{"value":{"entity-type":"item","numeric-id":966174,"id":"Q966174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$134DD7FB-B8A4-4E4B-9FAE-C923C1F81929","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$57A7F1E0-A677-41EF-A359-0DE2E98B3431","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24212091f138c83e2462dc5fd1f330307a161fb5","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2006.11.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q2479473$1266DBEC-9593-4F4C-9A44-A008AFB1F43E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee46268eea47beb399ee51e6fac60979f64c0743","datavalue":{"value":"W2078540027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479473$DFFDD9AD-28D8-43F0-BAE2-3906DCD702F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"96f3760374efc121f9066e6b2938749ee92522f7","datavalue":{"value":{"entity-type":"item","numeric-id":5897236,"id":"Q5897236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$BE3C8AA3-D1E7-4113-A7B7-DB66F39265B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a15ceaf12e673bea3f5e80c815f6dd9194e0039","datavalue":{"value":{"entity-type":"item","numeric-id":1423583,"id":"Q1423583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$C791C505-D142-4BBC-AF25-A1EE8C0EF66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffd3bc7a2da26b1a8f6e371186d08420752388f6","datavalue":{"value":{"entity-type":"item","numeric-id":4279195,"id":"Q4279195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$81018EED-8958-41A1-AB05-75F09F8B4483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee48772953085db35d619c153f333bc1d533218","datavalue":{"value":{"entity-type":"item","numeric-id":2565690,"id":"Q2565690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$FC54F609-938D-46AF-9774-7B53AD3CAECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53f7902224b58b0caed46ac823765d8213f69279","datavalue":{"value":{"entity-type":"item","numeric-id":2545109,"id":"Q2545109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$F88173C1-B18F-4A9D-80FA-25270265AB47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da7eaaae04a52671c77b3c3e5656d34042759636","datavalue":{"value":{"entity-type":"item","numeric-id":4717849,"id":"Q4717849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479473$BE213EB4-0723-4913-B19A-F7A4BEE9016B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51b77f9a6787023c4aa568c8ec08f9aaa27a46ad","datavalue":{"value":"10.1016/J.COMGEO.2006.11.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479473$4A3F51CC-608C-4794-AEE9-832D3E656AFF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee5c73418b617593dacd68938d71b75e3f8fbfd","datavalue":{"value":{"entity-type":"item","numeric-id":5449751,"id":"Q5449751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f116f47e76a6eb46714c52dd4442d71bbffb681","datavalue":{"value":{"amount":"+0.98948526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$47CA6E57-4E97-489C-AC79-3858141AF718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f154b963f06fdc7cbdfcf0ddf6c0e57aa106b81","datavalue":{"value":{"entity-type":"item","numeric-id":2565690,"id":"Q2565690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fcb9de02028fadd89b26b6c97e58d3f9d2ad778","datavalue":{"value":{"amount":"+0.958153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$EBC42D63-9A63-449F-949F-F3B8510173F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f9801cd7fccfc1b0ed616404bde3aad822a46e3","datavalue":{"value":{"entity-type":"item","numeric-id":2341719,"id":"Q2341719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ed1c6e1b7181ac516bce87bc02d4cbe46068347","datavalue":{"value":{"amount":"+0.9049315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$E1646AAC-C225-4D5B-9AEB-8486B078A6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ebb4e10d4657a40c05aa9b3d2e1b2a3ee06da4e","datavalue":{"value":{"entity-type":"item","numeric-id":2843275,"id":"Q2843275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff9159cdef52c52973b05d8b8e88ff3dd0e1dd3c","datavalue":{"value":{"amount":"+0.9015083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$88DA8D86-5680-4A40-B819-832F45CA563F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fea683f04a8dcedb0d86d6c63b6cd3c52785db31","datavalue":{"value":{"entity-type":"item","numeric-id":4394435,"id":"Q4394435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf94d55ebaef1bb0ada2a10f504222706d566501","datavalue":{"value":{"amount":"+0.88990414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$45F0A7D1-A215-4447-94FB-99ACDFC61792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb9df6eb6bff16151c9e08baee9c41b26d0db86","datavalue":{"value":{"entity-type":"item","numeric-id":1405822,"id":"Q1405822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd14852a66aa0c9769eaea1fe5b45fd6ff16f87","datavalue":{"value":{"amount":"+0.8891976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$8716843F-07D8-427F-8B20-12098A21B58B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1200185d006fd0c023c160bdb9261a8952b3a8ab","datavalue":{"value":{"entity-type":"item","numeric-id":1365058,"id":"Q1365058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca4e1c5741a14512b10caeae216cad247ddf9dab","datavalue":{"value":{"amount":"+0.8782182","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$B51F7C89-79BF-4039-983F-CCED1B527FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c944c4283b5336964396cb7c2c43bddb980b069","datavalue":{"value":{"entity-type":"item","numeric-id":5272929,"id":"Q5272929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35d97ff3678976fdb1e35dc75003f122f462a283","datavalue":{"value":{"amount":"+0.87651205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$49077991-3A24-41F3-8E74-925DB04C3A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc1b0a4e44afceaa2fa5dba773264eab250a3116","datavalue":{"value":{"entity-type":"item","numeric-id":2767414,"id":"Q2767414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"363626c669fe2112a317dad786973e84191d2684","datavalue":{"value":{"amount":"+0.8751118","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$3EC8337B-E9E9-4CB7-930E-EB20C2B34114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0030e2b6411e010d995042d7d7ad723893417eb1","datavalue":{"value":{"entity-type":"item","numeric-id":426086,"id":"Q426086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ee4d23330529a91b8efa12659088c2cc3b5c6f6","datavalue":{"value":{"amount":"+0.8750179","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2479473$0F5704F1-B857-4B2F-B3AB-174432B2F4E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient algorithms for the \\(d\\)-dimensional rigidity matroid of sparse graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_algorithms_for_the_%5C(d%5C)-dimensional_rigidity_matroid_of_sparse_graphs"}}}}}