{"entities":{"Q1428112":{"pageid":1438852,"ns":120,"title":"Item:Q1428112","lastrevid":67728732,"modified":"2026-04-12T19:31:59Z","type":"item","id":"Q1428112","labels":{"en":{"language":"en","value":"Efficient generation of triconnected plane triangulations."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2056259"}},"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":"Q1428112$E2B46F08-727A-4042-A5B1-91AE0C72CB7F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8337be7418d893cd89f0ff7233247c4d64158ba","datavalue":{"value":{"text":"Efficient generation of triconnected plane triangulations.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1428112$A956F6B8-9E83-475A-9768-F74124333610","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3fc9300c0bef7726c2421f6305619e4047f0978e","datavalue":{"value":"1041.65022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$62D43874-681F-4C88-A02B-A2F195C7106D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d644e433a66335990abf68d3b7d722a950cb6450","datavalue":{"value":{"entity-type":"item","numeric-id":238445,"id":"Q238445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$21B37333-632A-482C-9C43-56DBE2B1FA4B","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":"Q1428112$F7469CB9-C53E-41D0-A6D3-C70E622DCA02","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"947fc07e6e3c9508b7adeaf87fe542c1ae2d0058","datavalue":{"value":{"time":"+2004-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1428112$5079FB93-F5F5-47F8-BD64-6F20AF4D3002","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e59045c46e8881a9e0103369359ca1d296e82c7a","datavalue":{"value":"Generating all graphs having some property without duplicates has many applications. The author gives a method for solving such tasks. It is an interesting open problem of this paper to use this method to give an algorithm for efficiently finding triangulations of a set of \\(n\\) given points on a plane or to solve other ``generate all of something'' tasks.   Among others the following results are given in this paper: A ``rooted'' plane triangulation is a plane triangulation with one designed vertex on the outer face. A algorithm to generate all triconnected rooted plane triangulations with at most \\(n\\) vertices is presented. The algorithm does not output the entire triangulations but the difference from the previous triangulation and generates such triangulations in \\(O(1)\\) time per triangulation without duplications. All triconnected rooted plane triangulations having exactly \\(n\\) vertices including exactly \\(r\\) vertices on the outer face in \\(O(r)\\) time per triangulation can be generated without duplicates. An interesting result about such non-rooted plane triangulations is also obtained. All maximal planar graphs can be generated in cubic time per graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$36F8B310-2D9D-40AB-8780-20E543417E85","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$891B9044-BCD4-40A0-BA56-FEBF427E9191","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$CBF4E851-EF1B-42AB-A48A-AE3AC7909BD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$9ADE7C91-9186-48D9-95A2-CFBC45B7F1B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a729f401171a771b3aa2c3ce466e60b13d6ef295","datavalue":{"value":"2056259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$E5C56F27-DC56-4604-94E3-D9343960F23E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee89f50ee4e27a4a7c930c71a61ad98ddf8ae85","datavalue":{"value":"plane triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$3C2346AF-168C-48C3-AF98-D8F6B6057948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ffda2e4fffac71b2b14b11d965b9da434d71245","datavalue":{"value":"rooted triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$F03FEAB5-A1FE-4842-8818-C0EBE20B6067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$AD5918FF-39CC-488D-8AF9-A5CDCB9EA8C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b63a980a2cd6a8bd5151bdb1879e3992ffb722f8","datavalue":{"value":"listing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$2ADA59AA-68CE-450E-A87C-C76FD325D8F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1995fdcdd1355348390b1088e3d0a9b9e24f093d","datavalue":{"value":"plane graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1428112$CFE44057-4CD0-4FDC-840C-69026B589217","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":"Q1428112$801BE18A-9F9D-4900-8116-B49818BAFFB0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b1646e98190ad1389f8d9d123896b0c1c9d7341b","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2003.06.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1428112$110ECEFD-707F-41B4-866A-DFC105848032","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e73a340c1e2509e643cadf3fd91e2769e888896f","datavalue":{"value":"W2024428991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$2625F4F6-57DF-4BB9-8D03-2F5826179A57","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a12f7094fd2fa22f5a9b42e8cb2cc28791606a2c","datavalue":{"value":{"entity-type":"item","numeric-id":1817003,"id":"Q1817003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$6C816D06-9AB7-443D-88B1-3B620055BD50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"943325e1f000fe2507d47c48c5ec5c9cec1f5256","datavalue":{"value":{"entity-type":"item","numeric-id":3900084,"id":"Q3900084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$53F5282F-63E7-450E-8211-FA1FB82B369C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fd0b57ecaa4d09d1c4310d93fe4bf1cf877c36f","datavalue":{"value":{"entity-type":"item","numeric-id":4282002,"id":"Q4282002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$983270DA-DC8A-4D7D-8236-F46DBC3212DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cc4a7ecc6049fce452aec78e65ad081d5e7ec","datavalue":{"value":{"entity-type":"item","numeric-id":4148000,"id":"Q4148000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$1AB02CE9-DBDF-4A8C-8EB5-0804868544B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91b6b05eb0a4d1550e843f0fe191416f5cc3ccc7","datavalue":{"value":{"entity-type":"item","numeric-id":4522102,"id":"Q4522102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$8BC00B13-F245-4878-9203-2E265C7A171A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d205c7cdb3a7fdafed1a35935efbe3fe8a3f01","datavalue":{"value":{"entity-type":"item","numeric-id":4386451,"id":"Q4386451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$B829933D-7D6F-434B-B839-70EB0E1902CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9627ee40d6098655c0a507d4ebe4c72c9f6937fd","datavalue":{"value":{"entity-type":"item","numeric-id":4725765,"id":"Q4725765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1428112$35DEC682-6C49-40CC-AEB3-28C5FB367442","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ae938ea402f27a1b5869319d85751d299dbbeba","datavalue":{"value":"10.1016/J.COMGEO.2003.06.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1428112$78CC5848-9603-4FC4-B96E-6F82786EE226","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3275acb121facb773c17326d4e4ba225c75faccd","datavalue":{"value":{"entity-type":"item","numeric-id":4551355,"id":"Q4551355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72ac3f42c46aa0731c5ccc10a3d16051305860bd","datavalue":{"value":{"amount":"+0.9706372022628784","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":"Q1428112$C085891A-DB9B-4251-99A8-8EAB7C6C5AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"997bc3f8e8227a8ea58dbc650ee77594361feed1","datavalue":{"value":{"entity-type":"item","numeric-id":4535037,"id":"Q4535037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b55db6eb55ae45b9c4b0165ce293a431c176a30","datavalue":{"value":{"amount":"+0.9164212346076964","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":"Q1428112$557B09A9-8EE6-47D6-8449-FFA2C58281F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b01acbc1d643a813bc11a0703598779177edbb09","datavalue":{"value":{"entity-type":"item","numeric-id":5896900,"id":"Q5896900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34f0bbb8b47bc05b326ab8f2220717f5e9ff3957","datavalue":{"value":{"amount":"+0.9097544550895692","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":"Q1428112$41F1A11E-560D-44B3-A939-FB70365E164C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a6d933446e143f565d2a4b53f6116c72cd83238","datavalue":{"value":{"entity-type":"item","numeric-id":2865036,"id":"Q2865036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55eae168c0e2fa0417c69d40c66e14379cd71913","datavalue":{"value":{"amount":"+0.9091857075691224","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":"Q1428112$AB32F96A-31C8-47EC-9C8F-76AC75D3A391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e29ef3d95b947f7c02de321fb83aa6f4f2c7719","datavalue":{"value":{"entity-type":"item","numeric-id":1817003,"id":"Q1817003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e59ddc619cf8f8491928bd3ef33d7c6b5fc46cdf","datavalue":{"value":{"amount":"+0.907769739627838","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":"Q1428112$3F8E3037-AE58-4582-9485-25CEA9A43D0F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient generation of triconnected plane triangulations.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_generation_of_triconnected_plane_triangulations."}}}}}