{"entities":{"Q1116348":{"pageid":1127097,"ns":120,"title":"Item:Q1116348","lastrevid":69678888,"modified":"2026-04-13T08:39:47Z","type":"item","id":"Q1116348","labels":{"en":{"language":"en","value":"Shortest enclosing walks and cycles in embedded graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4088948"}},"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":"Q1116348$F18F5BE7-DB39-4D28-8BAF-6CA9C5E25001","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec250947ba1c4079088a915e1efddd4294260cb1","datavalue":{"value":{"text":"Shortest enclosing walks and cycles in embedded graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116348$08DB41ED-0F25-4A79-B4F9-374D7CB34A06","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49c590d2a17f1be78996d54b44c11c7cf9c661ae","datavalue":{"value":"0665.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$2D62E7C2-CCB9-429B-A2A7-557D3F4359A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"300829a9ae83c5a34a77be6344cbb60cafd59066","datavalue":{"value":"10.1016/0020-0190(89)90129-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$0B7806C4-7815-4DD3-8156-231E64801D15","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff4ba1aa663765d237e84b0e391fae178ff94609","datavalue":{"value":{"entity-type":"item","numeric-id":1116347,"id":"Q1116347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$B3617C1F-D7EC-4852-8E94-0C21F476540C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$BE340967-5AD7-4585-9288-532D50E245B4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1116348$3FF06E7A-17B9-4300-B409-82AAD52A6EC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"563c0d8ddccac1872462058a6125543821d76d19","datavalue":{"value":"We consider the problem of finding a shortest closed walk (SEW) or cycle (SEC) surrounding a given obstacle O in the plane and chosen from a nonnegatively weighted graph G with a fixed (not necessarily planar) embedding in the plane. We show that SEW is polynomial if O is connected and NP-hard otherwise, that SEC is polynomial when O is a topological ball and NP-hard if O is a general connected region, and that both SEW and SEC are polynomial for general O when G has a plane layout.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116348$64B178FA-AB92-4E4C-A4C9-2C3C47C0E503","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$56F7088D-F681-455B-A866-325AD0DFBEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$BD4358A3-E346-4A8A-8293-7D381C746E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$23B65AE7-918C-4E96-A60C-2BFE9197575F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$05683CB2-9826-474A-B598-D405EF08880D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$99922660-82C1-48E5-963E-99DC0CDC1C45","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1f272300feff5e79ed4ad260ed6f2faac38abf0","datavalue":{"value":"4088948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$0569E6C6-F36C-42E6-9791-E284CFE9B252","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9ac622ac7e0b1cefa635caf8f3459538b24541b","datavalue":{"value":"enclosing walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116348$9CB916AD-8667-4F96-A3DA-0BE2F8957588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6f0fd504aeefaeff6865a80cdcb4c21c32e56fa","datavalue":{"value":"enclosing cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116348$3E8873B5-D20B-4F62-A2E8-B70CA302C109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"faa4d3aaadaab4d99921b3d3565ea12b28aad73f","datavalue":{"value":"embedded graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116348$0C31F102-916D-4DBD-80D8-02539E22F7AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66b1e6938a358c4d5326f21b74cba7bf515efeb7","datavalue":{"value":"plane graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116348$34F3910D-1BD2-44D8-9764-7E385AF8CC62","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":"Q1116348$E3699B59-7486-4655-89C4-1CD36E8644A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ecfc792ae4ba37efeaedf51153026cfc9ed27484","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90129-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116348$774153A0-64CB-4F55-80F7-0491C67EFA4E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c63137e810563232fa763cf04697b1de9dec4c98","datavalue":{"value":"W1976021853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116348$A831899F-ECF9-4FBA-9C19-DDDDD559F686","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd7135f3314a1a9a9cd8efb8644e179b99d9907","datavalue":{"value":{"entity-type":"item","numeric-id":5535091,"id":"Q5535091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$EE271A6C-390A-4D6A-9829-59411122C679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c51a0463b95f55a754d0b2de6a2b6f27abf3ea4e","datavalue":{"value":{"entity-type":"item","numeric-id":3832585,"id":"Q3832585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$C9CD4E6C-64C9-434B-AF6C-25B3351330A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$3D01D164-4A86-44F1-85A0-1841CF3D34C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$F5A57410-6E0A-4750-8E0B-736C40C8A3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f33e086a7a96a72aadab83cbb413d1e9523b8dd","datavalue":{"value":{"entity-type":"item","numeric-id":5557005,"id":"Q5557005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$F8A12A64-F7DA-4455-9FBB-1D1F11540786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0172ba1b6d6a71dfada5ea07ead90ea9385b47a4","datavalue":{"value":{"entity-type":"item","numeric-id":3789369,"id":"Q3789369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$74B8670D-AC4D-40E0-BB7D-AD0D6381FBC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3bd4903ca96601448c89bbb60098c06b73210b","datavalue":{"value":{"entity-type":"item","numeric-id":3816989,"id":"Q3816989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$85381073-B6EF-446C-BB55-86763C526AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116348$AE801FC9-0F42-49CD-BC7D-E13AAF715583","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5727837e95d1dff59928272e4a0245ca45d69f5","datavalue":{"value":{"entity-type":"item","numeric-id":1283782,"id":"Q1283782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecea79e8c53a4fa0a177c2ee2fa3cf33d6414a72","datavalue":{"value":{"amount":"+0.831244707107544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116348$5D3CFE0A-B542-436F-B1C7-CED3C73C8489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0e299621fe49d13fdf7c6c35e582779e89e3a7d","datavalue":{"value":{"entity-type":"item","numeric-id":4633873,"id":"Q4633873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46775d7fe666190918a2f019dd587f5229e3b73e","datavalue":{"value":{"amount":"+0.7979528903961182","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116348$8BC10246-E53C-423C-A23A-C4FF6871CFF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"299acf7a13948367f066e1739ca70d1a8cdf501a","datavalue":{"value":{"entity-type":"item","numeric-id":2930300,"id":"Q2930300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d33941c903602c615129368847f16fc5b3bf72ef","datavalue":{"value":{"amount":"+0.7979527711868286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116348$699D1082-F54D-4859-9796-B5465382C3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac66abf4684b3639b91efcf957383c1181a3c229","datavalue":{"value":{"entity-type":"item","numeric-id":3832585,"id":"Q3832585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88f1ad4c23b6831fdba18b969e5e59da9a1c8009","datavalue":{"value":{"amount":"+0.7806889414787292","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116348$64F8E0EB-A8F6-4BDD-8E5C-6256E2EF5CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40e863cc6956f0533dc8258685e246bc9ace37b5","datavalue":{"value":{"entity-type":"item","numeric-id":5365044,"id":"Q5365044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8362ad4e56720c85dd258a37f2631c75de72af0","datavalue":{"value":{"amount":"+0.7670497298240662","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116348$F9A683B0-054E-47BE-89D1-3497499662D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Shortest enclosing walks and cycles in embedded graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Shortest_enclosing_walks_and_cycles_in_embedded_graphs"}}}}}