{"entities":{"Q1120582":{"pageid":1131331,"ns":120,"title":"Item:Q1120582","lastrevid":66170883,"modified":"2026-04-12T08:01:28Z","type":"item","id":"Q1120582","labels":{"en":{"language":"en","value":"Embedding planar graphs in four pages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4101207"}},"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":"Q1120582$D2CE8486-E7E9-4CB3-ABD4-F25C9EF5C646","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a9bbe70c3b2c97e99a779e79234ea665073ac224","datavalue":{"value":{"text":"Embedding planar graphs in four pages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1120582$82B32D60-6E66-4E53-BC14-53623B60BC88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51a5a17a6dceb52cec70ed35aa92c735fcf23e47","datavalue":{"value":"0673.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$155F3637-EA9E-4C66-AA11-F45F66664097","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45a77a350ae8cdde069f106ebd261c542ec441a4","datavalue":{"value":"10.1016/0022-0000(89)90032-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$4577A192-8926-409E-A94A-B31ED1317886","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$4F6E2B4F-DCB4-4338-A272-DC858CFCF75D","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":"Q1120582$26F434CC-9926-43DF-B8AE-D6D05A547BEA","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":"Q1120582$02DB3CA8-08D1-48C0-8C0B-B2BB6975BA97","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f42b03a206fecd56bd58317dde115a43af30ec5c","datavalue":{"value":"A book embedding of a graph is an embedding of the vertices along the spine of a ``book'' (i.e., a linear ordering of the vertices) together with an embedding of its edges on the pages so that edges placed in the same page do not intersect.    The author proves that any planar graph has a book embedding with at most four pages. The proof is constructive. Moreover, a linear time algorithm is presented for finding such an embedding.    In another paper of the author (which is in preparation), examples of planar graphs are constructed which do not admit a book embedding with 3 pages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120582$B8887BC8-6F4A-40DB-8463-5735887CEBE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$2D05E448-D28D-4421-A1B3-2D6B00EBAD14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$F2D20693-2E16-499A-9545-3E505912D414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$F55740FC-C40D-449E-97C0-206A6C41D919","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5a29d807da5b886cdbe4fb9fa54519b4071b98b","datavalue":{"value":"4101207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$7FD9D9BC-162E-4F42-A327-8BBDEDC385B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24198b416556221c891927e28dc5bda70bfeb4d9","datavalue":{"value":"book embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120582$9BD9A5A6-0B07-46FD-A5AC-63708A4D98DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120582$00C0FD2B-E40E-46F4-9020-638F448CECF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120582$F5883867-108B-422F-A96D-CBA8A5826A70","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"887c54283e16d6432f89e457f93f4a2b0a4d78f2","datavalue":{"value":"Q56689179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$F5F87E0B-C1C1-4AB2-A83E-3A9649D8AF8D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$B80C38CC-1A48-4B81-AEF3-280A2872B640","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":"Q1120582$79468887-BE77-4692-853D-0E4A500C47E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"04099b6d08eba8d5ae86cf765ca1f4530b361427","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90032-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1120582$0051CE91-6D19-4D06-B90A-7974BE2AA8C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17d87ebffff788a3153c9d18c0f949d8e3c2bff5","datavalue":{"value":"W2119115989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$1C2B2C40-CF9E-4DF9-9ACF-EF919EDD2F58","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2860b21ec28091243d6f8b5601ce1d563a55934","datavalue":{"value":{"entity-type":"item","numeric-id":1136775,"id":"Q1136775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$B189564D-5C64-4706-A8B4-9019EA720A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3feabf7738470c05cc9bc57fe6125054132512","datavalue":{"value":{"entity-type":"item","numeric-id":5684962,"id":"Q5684962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$F25AFDB9-D252-4566-9BA7-3C65836EFA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8966655ecbb1863d7d15b1de7a7a366acdd2bc41","datavalue":{"value":{"entity-type":"item","numeric-id":3964622,"id":"Q3964622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$0028D2D6-01E3-49CC-A160-09B35071FD7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$4C91CCDC-4DB3-49B7-B522-093FF269F07E","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":"Q1120582$2DCB12C7-F067-48FE-AA9F-FFD70D519F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5965d2d8a4d84d2c8efe1e517c0f4ece3c4ab834","datavalue":{"value":{"entity-type":"item","numeric-id":4207598,"id":"Q4207598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$16FE2C57-0679-440A-91FD-FFD8FD7702DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56f18eaeea7ef4060e43c7c2188cd545ab9e0d69","datavalue":{"value":{"entity-type":"item","numeric-id":5654999,"id":"Q5654999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120582$40DF9F82-7EEB-4496-81F3-22F9A05B2326","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"9f5d95a6c2ed9978fcc6b26f44ff517cf39ef6d3","datavalue":{"value":"journals/jcss/Yannakakis89","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120582$478A46F1-FFA9-45CB-B576-60E55E1547D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d186aaa6a6661b6104ffc52f18c554a28b310edc","datavalue":{"value":{"entity-type":"item","numeric-id":5120157,"id":"Q5120157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d49aac33556433f0386bbd6a3d3b50960b5154d9","datavalue":{"value":{"amount":"+0.9239327311515808","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":"Q1120582$C373ECD6-BF90-4EF0-884B-348B0445EAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d114db7b02c5c3fc293dcfd5ec936a59b3da7da8","datavalue":{"value":{"entity-type":"item","numeric-id":2185736,"id":"Q2185736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d65b1c029d0079e5d7c0153bd8d22e654ad6c0e","datavalue":{"value":{"amount":"+0.9031955599784852","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":"Q1120582$42BD00EB-1D93-485C-8D29-053B6D62011C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ca4ceeb1ca8b4768aa1dac961828411ce7279ee","datavalue":{"value":{"entity-type":"item","numeric-id":4207598,"id":"Q4207598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18d970a3646f0bd7e3459a25d4b3226c0e84ae3d","datavalue":{"value":{"amount":"+0.8625400066375732","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":"Q1120582$7D7658E8-4702-44B0-A1C0-E70C463FA1F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2c88aa87c3ae62427d0c684e54f1884aa94ecde","datavalue":{"value":{"entity-type":"item","numeric-id":2141323,"id":"Q2141323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a57c9183bd5074b6c43ebfc177e3b295d21eff38","datavalue":{"value":{"amount":"+0.8597793579101562","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":"Q1120582$3D8CF685-995D-478A-AE00-EF1002F9523E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Embedding planar graphs in four pages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Embedding_planar_graphs_in_four_pages"}}}}}