{"entities":{"Q1823959":{"pageid":1834701,"ns":120,"title":"Item:Q1823959","lastrevid":49311319,"modified":"2026-01-06T22:53:36Z","type":"item","id":"Q1823959","labels":{"en":{"language":"en","value":"There are planar graphs almost as good as the complete graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4116563"}},"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":"Q1823959$AA3DB882-DCAB-4586-985D-A7B07ADE12FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ccde052a419a23764ad2fd2a663251a84dafe523","datavalue":{"value":{"text":"There are planar graphs almost as good as the complete graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1823959$27B80974-5F39-4008-84F0-431C5FD9798B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"292f8e0f403ae898ba559da160cb1904a2b51912","datavalue":{"value":"0682.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$108F06B1-E262-4B1B-86BB-7813BCA1AAE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"698a10ee8107f1d09cc2f51e5667bf713a610b89","datavalue":{"value":"10.1016/0022-0000(89)90044-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$D0DF58E8-3523-4868-88BC-BA51E4FA0380","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"36f72dc458dbb68417eed24578c25b37631aa961","datavalue":{"value":{"entity-type":"item","numeric-id":598236,"id":"Q598236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$EC151F14-595D-495A-BC8F-447D8F333E98","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":"Q1823959$6F99C5AB-0134-4242-A234-DD2B7517F1B7","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":"Q1823959$56A1123F-B904-43A8-B0FB-6EF0BDF8E4F4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b044ca3b4e9e3dbf4639965ee455707d293a7abb","datavalue":{"value":"For a graph G represented in the plane (perhaps with edges intersecting internally) the length of a path joining two vertices of G is here regarded as the sum of the straight-line distances between successive vertices on the path. Given a set S of points in the plane, the complete graph on S has the property that for each pair A, B in S there exists an A-B path of length the straight-line distance between A and B. (The complete graph is unique with this property, if the points of S are in general position.) In this paper it is shown that there is a planar graph G on S with the property: for each pair A, B in S, there exists an A-B path of length at most twice the straight-line distance between A and B. The graph G is a type of Delaunay triangulation. It has 0 (ISI) edges (compare 0 \\((ISI^ 2)\\) for the complete graph). Applications are discussed to network design and motion planning.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823959$622FFEA7-A03B-4EEE-8D9E-2F2A741A8EDC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$54DE5817-E311-4F99-BDF7-04507F5204CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$9B0BF976-C9F5-4B57-8E4B-DD6D75F89F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$DD2C6DF6-C8C6-4B93-A1DA-7AA9B13C8DA7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fa81ae8a2dc132c236d6b9c697839f5e5b91452c","datavalue":{"value":"4116563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$91F2B90E-2AB5-454A-BB76-663EF23B0204","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02f02638e877858ad95b243d73969bd2182821e5","datavalue":{"value":"length of a path joining two vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823959$99EDC41F-AB00-4AE7-B1D5-03A9E70C0FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823959$F1EB99ED-C6D1-4A8D-852C-7B7B442809EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3fef632528beb63cbafa91e31a04a2eda4684bf","datavalue":{"value":"straight-line distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823959$2D60DBB2-F986-48DE-BD52-E9664B9ACB35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823959$84E8F6C5-31A4-4E52-B504-63AB3DF9527B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$BF247216-4B4B-4238-9179-60FB62BCB740","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":"Q1823959$26B4D89C-EE98-4172-B569-E536A0F2664B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee3bfda89ca0e4431d8fe4fb373e52c3bf9865d4","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90044-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1823959$AF3596C9-41B9-47B4-867B-66ED10D22945","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2df92ad561d32ee6c86103092befae2c06d41bd8","datavalue":{"value":"W2139391136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823959$9E0AC365-F59D-4FF9-80EF-68AFEDB4B816","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98686b48b8c2e08b48821e02e53348b40525712c","datavalue":{"value":{"entity-type":"item","numeric-id":1115601,"id":"Q1115601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$937D9481-DAFC-4EC9-A3CB-8B3F90E5612C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffc7c8b334d26c0686dd1a9b8ac5d7d5836aced","datavalue":{"value":{"entity-type":"item","numeric-id":584279,"id":"Q584279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$142BE547-8A65-4D5D-97CF-86FC1892280B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99114b1bd38a031039ee6a9bed0217048b0b5658","datavalue":{"value":{"entity-type":"item","numeric-id":1101224,"id":"Q1101224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$88D69837-64FB-44A0-B5B9-6FB0E9D0528A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"794e24faea6d10ca38a88bb803e4681f9768e955","datavalue":{"value":{"entity-type":"item","numeric-id":3883495,"id":"Q3883495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$AB2566BA-8CF0-47E3-A352-BB649EAED17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$05B1BE1E-506E-483D-9A9C-7CB81C62C7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823959$FF648967-FB26-4926-9C88-0F1BE89E9070","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae9265457434801ca8820d1969f219b520bb2bd2","datavalue":{"value":{"entity-type":"item","numeric-id":3484376,"id":"Q3484376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce3a48a178849ee2265696867976229f0421bbfa","datavalue":{"value":{"amount":"+0.9057525992393494","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":"Q1823959$8E8EAC9A-2DEF-4C8D-80D9-A040D697CA5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca4ce4d57473e07fd269ac94e89078694a830c4e","datavalue":{"value":{"entity-type":"item","numeric-id":1194346,"id":"Q1194346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bde0733717367782d2905070dded3debca2c302","datavalue":{"value":{"amount":"+0.8900935053825378","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":"Q1823959$2C876ECA-A110-43B3-8D54-D21854FA611B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d94563708aadb5a7ee8ac8dc9cd86c45abf1edef","datavalue":{"value":{"entity-type":"item","numeric-id":3484375,"id":"Q3484375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"217901f0053eaa2bf8cf76f7d50fd29257dbae63","datavalue":{"value":{"amount":"+0.8827705383300781","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":"Q1823959$FCE514F8-FEAC-44D2-BB9B-E82869494981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60201f2eb1ffc81fa0bba9389cba36fd6c129282","datavalue":{"value":{"entity-type":"item","numeric-id":584279,"id":"Q584279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc9d0ff43ab273c5a7b3bb35579af9657d85a208","datavalue":{"value":{"amount":"+0.8568113446235657","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":"Q1823959$4042092D-FDEC-4852-92DB-D12F1A2B2A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a49c5a5ff6c4c6dba67c346cd63298bf46217adb","datavalue":{"value":{"entity-type":"item","numeric-id":1186079,"id":"Q1186079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7ce2c2d84319379711abbf9338361888a6e244","datavalue":{"value":{"amount":"+0.819587767124176","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":"Q1823959$34833A1B-006B-49DC-B12D-FB20E452D647","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1823959","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1823959"}}}}}