{"entities":{"Q1114415":{"pageid":1125164,"ns":120,"title":"Item:Q1114415","lastrevid":49238389,"modified":"2026-01-06T20:11:28Z","type":"item","id":"Q1114415","labels":{"en":{"language":"en","value":"An efficient parallel algorithm for planarity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4083004"}},"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":"Q1114415$FC0BB3DE-EF5B-4820-8BAC-C85B09143303","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a9db01604d5ce0246c06583bd57796930bc365b0","datavalue":{"value":{"text":"An efficient parallel algorithm for planarity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114415$C6ADA93A-B5C9-4948-AA41-F2838D26EE3F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"198790aabb1591f930385b0ecf8b0add039238c3","datavalue":{"value":"0662.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$12DFF4E4-521C-4BF2-8147-F424410A942F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dba6c5468112f663e6c1591e87c4b5c842cb2bf1","datavalue":{"value":"10.1016/0022-0000(88)90006-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$93DA261B-4103-434D-9A23-BECBBFAEFFCD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10413c8ea0c7beda69819895822b5490416ae799","datavalue":{"value":{"entity-type":"item","numeric-id":1114414,"id":"Q1114414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$797C333C-8BEE-4423-A8AB-B305816BEB25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$432B69FC-85F2-4D33-AAC5-C72E88009534","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$D6A5AAB6-9B3D-4BCE-82AD-63ED67756596","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1114415$052F1F52-49E7-4FCA-9D5B-7504A6AED080","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f1eb35eed31b94fb6368daa3c7d8ef5545723ba","datavalue":{"value":"The authors give a parallel algorithm for testing graph planarity, and for finding an embedding of a planar graph. Their algorithm runs in \\(O(\\log^ 2 n)\\) steps on n processors of a CREW PRAM. This is an improvement to a previous best parallel algorithm due to Ja'Ja' and Simon. The new algorithm uses efficient parallel algorithms for manipulating a sophisticated data structure for representing sets of embeddings - the PQ-tree originally invented by Booth and Lueker.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114415$DC3BE135-9049-4E35-8315-9E6B60479BAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$FFDAA1A5-815A-409A-AA58-1E2F3D954091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$39BC38AC-6A34-43C2-99D2-3021DC7B46DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"271c2247db9a01db59498a95376bb14efb7562b1","datavalue":{"value":"4083004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$B2D60224-3C16-4CCE-8231-7E0B15A85D8D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114415$5FAD1929-5F27-4F70-B3DA-3C30F7E12BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c856145ef6cf7ef96d1f0755055e2ec6f5396f57","datavalue":{"value":"planarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114415$BFBEFF6B-A7BE-45BE-9230-91D3D754E98D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114415$A245A6F3-D8DE-48BF-87D3-C64F372817E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e59ac626b33db549bc8a94a3bacc0beb688ee58","datavalue":{"value":"PQ-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114415$67DAA88F-F21C-4C13-B0FB-627A312AB534","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$0687334A-ACE8-4062-9B70-974B28CB4766","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":"Q1114415$9A2A32F2-A3A9-46AA-BB7E-42E62908F7B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5a0890fcccc4bd64c3abec6e7e402552b9259625","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90006-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114415$85A84877-E0E4-4729-BF5C-CC6418C29CE4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"55a7efb894567f23afe4a528f78a3a0db97af7ec","datavalue":{"value":"W2148686552","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114415$4DBF1B89-B4D0-42BA-85C3-1F5708A76FD1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$80888DBC-7362-4425-B4E8-ED288C34E76B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$0E05EA27-632F-4A28-8DD3-CD0A270F05C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$B7DE52EF-0067-4D6D-824B-00E917025F21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e9482ac52774f29c3e0eabec830d52edd86da50","datavalue":{"value":{"entity-type":"item","numeric-id":1231771,"id":"Q1231771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$C446BFD6-B5E6-48FE-BCDD-E93500804FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$6FF939B8-0606-4669-AD0F-1994D3FE1BA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$E946F65B-68B2-466B-BCA3-B8F350EEF30C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668ede22aaf0f582cd852b85766ea7ff07a98da5","datavalue":{"value":{"entity-type":"item","numeric-id":3957959,"id":"Q3957959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$927D4A7D-196F-43F0-9149-7F4CD6C102C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43f71ca4911d5c4d499c201902ca5756549231d","datavalue":{"value":{"entity-type":"item","numeric-id":1114415,"id":"Q1114415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$305353AE-B5E1-4611-B609-D013BE5D95BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7871dc2cc85bb5a8983590b741f23a06f01bacee","datavalue":{"value":{"entity-type":"item","numeric-id":5596083,"id":"Q5596083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$47C5E813-4E6D-4781-8445-956551B3BE09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1fb25059117f6dfa64a3b394b3edcc67100b7f7","datavalue":{"value":{"entity-type":"item","numeric-id":4187325,"id":"Q4187325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$3BBF4E92-9763-40C5-B456-AB84C1A5800F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0b79f0a572dc4ca00a1807f9e3f0fb0bdc1aecd","datavalue":{"value":{"entity-type":"item","numeric-id":3727398,"id":"Q3727398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$1462E249-EAF4-4B7C-96A2-3800AE9576E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ca3e015d5a9a71c43e5d072fe10aa2d6bf2145","datavalue":{"value":{"entity-type":"item","numeric-id":4747506,"id":"Q4747506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$105F7AAD-B0AA-4C4B-99AF-0D4AA6E86669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bce2bdfdb4dbf1ae6829158b6e801d107e5884d","datavalue":{"value":{"entity-type":"item","numeric-id":3880860,"id":"Q3880860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114415$FEF65691-7D6C-46AC-8529-5935A3FBE207","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22fb1abfd8cd86ba1aa24ff2defaaf6989708d28","datavalue":{"value":{"entity-type":"item","numeric-id":3801100,"id":"Q3801100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61ef6f291101b153905aa6cef44852d2f18e527b","datavalue":{"value":{"amount":"+0.8541433215141296","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":"Q1114415$7B1BF968-739C-439A-BE4D-202D95E8E2D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86b66fa9c03a563599772cdb9ee5fb54bd7a9167","datavalue":{"value":{"entity-type":"item","numeric-id":4721660,"id":"Q4721660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26e31d1eedeb79605df8a53b5e274834722c8229","datavalue":{"value":{"amount":"+0.8445797562599182","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":"Q1114415$7B80E79C-62A8-4590-B8D2-368F3A9A6386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"224d938416dc4cb24cdc7e7036d2fc620d5f4673","datavalue":{"value":{"entity-type":"item","numeric-id":1083864,"id":"Q1083864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"630a80f67840f4254e2d83ee7e5f77fd7ca5c8cd","datavalue":{"value":{"amount":"+0.8390579223632812","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":"Q1114415$5AF2FFE4-C715-4B9F-A4CB-859568D49BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5470b3c02779dcd80e9c9f1296b859acee2bcb2","datavalue":{"value":{"entity-type":"item","numeric-id":582094,"id":"Q582094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b36770f3f673a332e5c87c921abeb90ecf22c44","datavalue":{"value":{"amount":"+0.8316783308982849","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":"Q1114415$E8097258-E4CC-4728-B699-32C75A31B06A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8503eb77c3227bbe25093a21679975da6b52cb4","datavalue":{"value":{"entity-type":"item","numeric-id":1960413,"id":"Q1960413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2af0965a035eb89852c52c8b8ed29176cac238e","datavalue":{"value":{"amount":"+0.8285354375839233","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":"Q1114415$A8584CF5-4E06-4EEF-8D51-0C20A34A3913","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114415","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114415"}}}}}