{"entities":{"Q1083864":{"pageid":1094616,"ns":120,"title":"Item:Q1083864","lastrevid":70075632,"modified":"2026-04-13T12:16:29Z","type":"item","id":"Q1083864","labels":{"en":{"language":"en","value":"A linear algorithm for embedding planar graphs using PQ-trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3978409"}},"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":"Q1083864$BD093B61-6CBC-455D-AF52-99766D5B7A35","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10b1e2114b0e9738e1e52558222fa62567e7b30d","datavalue":{"value":{"text":"A linear algorithm for embedding planar graphs using PQ-trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083864$43CA46CC-2661-4BDF-96E7-28D628E3EC2C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94b8d111aba351c6b55be52c4e4bd0f3c4bb2b48","datavalue":{"value":"0605.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$0C1F1BA8-7EFB-46A0-888D-74370FA74574","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9618fe7999da30b1d3441d2aa1ab9736c34782be","datavalue":{"value":"10.1016/0022-0000(85)90004-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$48859C75-2F17-414C-B794-266AAE69AF6D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ee68de2af4277a285837f24c0d6ec9f5b26f572","datavalue":{"value":{"entity-type":"item","numeric-id":205117,"id":"Q205117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$13CC508F-8F6E-41A2-BD8F-7A09FA1E82F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da93d7c45d552338138e673e141df03679ac5cb5","datavalue":{"value":{"entity-type":"item","numeric-id":226821,"id":"Q226821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$305A69AC-F71D-4352-8A1E-A00F51C53DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a0bc7897e0144ac66898e0d2470482a8110d854","datavalue":{"value":{"entity-type":"item","numeric-id":1083862,"id":"Q1083862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$0B341BC3-8397-4D7B-8003-C7B61B0B8E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"827a28798d036f082aec100fa8a91a834ddbcb07","datavalue":{"value":{"entity-type":"item","numeric-id":1083863,"id":"Q1083863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$D18316CD-420F-4CC9-A237-EA64FF6988AD","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":"Q1083864$D93BC9E1-D96B-46C0-8396-C3410709E22C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1083864$4DA301AD-DE75-40AB-9EBB-4DEE4DDCFB2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"011480dc4e581531432303786311270a8dd572c3","datavalue":{"value":"This paper presents a simple linear algorithm for embedding (or drawing) a planar graph in the plane. The algorithm is based on the ''vertex- addition'' algorithm of \\textit{A. Lempel}, \\textit{S. Even}, and \\textit{I. Cederbaum} [Theory of graphs, Int. Symp. Rome 1966, 215-232 (1967; Zbl 0197.502)] for the planarity testing, and is a modification of \\textit{K. S. Booth} and \\textit{G. S. Lueker}'s [J. Comput. Syst. Sci. 13, 335-379 (1976; Zbl 0367.68034)] implementation of the testing algorithm using a PQ-tree. Compared with the known embedding algorithm of \\textit{J. E. Hopcroft} and \\textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 21, 549-568 (1974; Zbl 0307.68025)], this algorithm is conceptually simple and easy to understand or implement. Moreover this embedding algorithm can find all the embeddings of a planar graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$3245624F-02CE-4D00-8A77-708F13E0DDDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$0F98AB5B-2FBA-4F33-A44D-E7891AAB2E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$86303A09-FC5C-40B4-A584-0670AE45D701","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"21e2d33fdae5a0f529ac06357a8086a964cff5a6","datavalue":{"value":"3978409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$BEA6EAC0-DE15-4382-A94A-5365B4DAABDF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c8ac636bcb75e32e48f3c1767ab0375302759e1","datavalue":{"value":"vertex addition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$499E925F-50B9-4C05-9804-EE797A2D7283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a49464e2d7be3b5ec6afa9a7b997ccf87f3adaab","datavalue":{"value":"linear algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$034922C1-93F6-4B41-81F9-9729EEE1EC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$8F9D4F18-BC2E-4B03-9523-C4760B823671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3744d15beadc0dbcb2f518132d24966a53bb56b","datavalue":{"value":"planarity testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$A9814B7B-07E4-47E7-AFC0-42EFAE07E2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad6f15293cceeb03d43a8c6b6ceac89511aa7c31","datavalue":{"value":"embedding algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083864$0C8B36E0-97CB-48BA-9D5D-8E8A6D863944","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"689d7df6800df1f19ef5f52d3fb458ad9b1d2faf","datavalue":{"value":"Q60304238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$450A2E17-0CB0-454E-BDB3-5CFEA65F1723","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":"Q1083864$E3B74A63-7D6C-44EC-8570-CDC14E7FB718","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6964f6e71dc6dfb4630ee0a762772b7a82c0dd35","datavalue":{"value":"https://doi.org/10.1016/0022-0000(85)90004-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1083864$AB756DEA-A2A3-415B-8C3E-6B31B1C05FBC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b844b336b8559139d2d91937d98e8b1e093b974e","datavalue":{"value":"W1964700557","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083864$2F4B74B2-6E7D-4573-826D-13000C60F9C2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccc51fd08844ba913c418b8f29bf3082dcb02e6b","datavalue":{"value":{"entity-type":"item","numeric-id":3283487,"id":"Q3283487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$73CA5DBC-DD22-400B-A63F-499BC688CB20","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":"Q1083864$2358DCFD-65D3-41C5-9D65-7E7550EBFB4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a50d921ac2110ef5bff54a68385e98098295c2a4","datavalue":{"value":{"entity-type":"item","numeric-id":3220608,"id":"Q3220608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$4697DA20-ADD4-4DFA-A9FC-F2A2F13F2CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$D2C0F1B9-FE4B-4516-B66B-C643A8623EB6","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":"Q1083864$E33DA6EF-04AC-4F49-A709-46FD31C9C1AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$4F666C0F-480B-4E48-B31A-920B7378B220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083864$E0CD805F-D39B-4216-9AB4-45898A6E460D","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":"Q1083864$20CDD86A-1A77-4E13-BDB8-7153983A5993","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":"Q1083864$D1E1100E-13AC-4749-AD5A-D2D4A02BD73B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953dfb50ca44d9baf63578c01519217813b97256","datavalue":{"value":{"entity-type":"item","numeric-id":4252282,"id":"Q4252282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc8b4d8fccdad532dfd8e249268b41022c3530c","datavalue":{"value":{"amount":"+0.9138494729995728","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":"Q1083864$3393A22E-3171-42AF-ABA9-3B2849003725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15283d49a8f1054291da5ec0eb1c08b41070a4d2","datavalue":{"value":{"entity-type":"item","numeric-id":3183081,"id":"Q3183081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc8b4d8fccdad532dfd8e249268b41022c3530c","datavalue":{"value":{"amount":"+0.9138494729995728","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":"Q1083864$E1CA623D-9F17-4823-ADD2-80A8DC5939D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"125592b4fd5239c8cdcadbd9e5c8fe5ead9cb4a5","datavalue":{"value":{"entity-type":"item","numeric-id":5300998,"id":"Q5300998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"938d4bb189bc897d9a7c7cbf8b31262ef986400e","datavalue":{"value":{"amount":"+0.8982564210891724","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":"Q1083864$00BBFF16-DD31-4BD7-9DDF-1D01F4740641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ee830918743f9f66dcab9e7b03cb71c597de0d0","datavalue":{"value":{"entity-type":"item","numeric-id":3801097,"id":"Q3801097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cd2afc8831d9037722e6feb0d4bd9528b2a229b","datavalue":{"value":{"amount":"+0.8788230419158936","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":"Q1083864$4064D58B-06EE-40F6-8EFD-552F63EF5028","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":"5d7101ff1c40e93d9e911c959b93a42d9a3ca303","datavalue":{"value":{"amount":"+0.8615193963050842","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":"Q1083864$F1223CFB-478B-49B3-92B3-34EF0C4147E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear algorithm for embedding planar graphs using PQ-trees","badges":[]}}}}}