{"entities":{"Q1355197":{"pageid":1365936,"ns":120,"title":"Item:Q1355197","lastrevid":70228332,"modified":"2026-04-13T13:21:13Z","type":"item","id":"Q1355197","labels":{"en":{"language":"en","value":"Grid embedding of 4-connected plane graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1011313"}},"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":"Q1355197$53A82E14-4F16-4009-9224-76A9831EE4F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0f2994b6f6303cbef8e7ffc4257c7e7e942e9852","datavalue":{"value":{"text":"Grid embedding of 4-connected plane graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1355197$140AA20D-7B39-477F-8D1D-3860DE5C3856","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61d3e97e5ddaa7e7d4e5074630f43b97bc9e3d1c","datavalue":{"value":"0877.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1355197$9C6645FA-2542-456F-A53A-ED8E5640F2C2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e1d67b9e870cf6c1455eb287b8d492096fd970c7","datavalue":{"value":"10.1007/PL00009290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1355197$5D4C3AE2-907D-469A-AADD-132C4D37FB3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5e3e4a8492e84e11f7f67bea925623ed4dc895c","datavalue":{"value":{"entity-type":"item","numeric-id":237645,"id":"Q237645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$969A3E85-0CA6-4CA3-AFFF-3CE9D1CD484B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$8C405756-194D-46EA-8C0C-35B042AD358C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5392596ed00365b9040485b26d567df955774c4a","datavalue":{"value":{"time":"+1997-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1355197$9B672E76-F448-47DD-80B4-EF1A3705A12C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e883ad0da44753eb0ac14ca0bb79ba85cf8a25e","datavalue":{"value":"Let \\(G\\) be a graph represented in the plane so that each edge corresponds to a straight line and any two such lines intersect only at common endpoints. If each vertex of \\(G\\) corresponds to a point with integer coordinates \\((x,y)\\) where \\(0\\leq x\\leq n\\) and \\(0\\leq y\\leq m\\), then we speak of an \\(n\\times m\\) grid representation. It is known that every planar graph of order \\(n\\) admits an \\(n\\times n\\) grid representation, and that there are \\(n\\)-vertex graphs which need at least a \\(2n/3\\times 2n/3\\) grid. It is also conjectured that such a grid accommodates every plane graph of order \\(n\\).   In this paper it is shown that if a 4-connected plane graph \\(G\\) of order \\(n\\) has at least 4 vertices on its external face, then \\(G\\) can be represented by a \\(w\\times h\\) grid where \\(w+ h\\leq n\\), \\(w\\leq(n+3)/2\\), and \\(h\\leq 2(n-1)/3\\). Such a representation can be found in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1355197$DC4ED508-E6D7-4032-9C5D-0946B509D1DA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"abf255b967b94e917e05e1834cde56652b9b0e09","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$37A6AF82-BB9E-42AE-9BEB-C3A6A7CD6BAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1355197$EB5CAE5C-040C-43C0-9D22-E45791816E78","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7864f2775aa9e82158fc33708a7229a1cf162d25","datavalue":{"value":"1011313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1355197$C7D178C5-334B-44D3-8BE2-D8142F9B6604","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1355197$BE2645D5-B708-4F15-A6E8-516D1DBDCD58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e7193098d8135b0110a5a77f74336bfcb62798c","datavalue":{"value":"grid embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1355197$D2ED17EF-DF69-4C55-AF22-D619AB28B104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8a838e760756c67b624537062d93adb47e799c9","datavalue":{"value":"grid representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1355197$341216EA-F616-4AA2-88A6-F3C713C177FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1355197$D66E6BB1-F3AC-42A3-9D8C-D6CF2467E723","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":"Q1355197$B83B8B11-2C9B-4F66-B3C3-6F5EDF452643","rank":"normal"}],"P223":[{"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":"Q1355197$6189909D-A376-4B54-951E-3582690B647C","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":"Q1355197$4DFBA6E9-5CF2-4289-B08A-6884F71A085B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c441ecc981b4626a9c2189897cdabb0bac07dc2e","datavalue":{"value":{"entity-type":"item","numeric-id":673676,"id":"Q673676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$F19087AF-24E7-4652-A685-00DF5366FFED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"795d5053d33d6922d114b0161a566c61fae789ce","datavalue":{"value":{"entity-type":"item","numeric-id":1337400,"id":"Q1337400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$49A4750E-B265-4964-AE01-8863EDC181CB","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":"Q1355197$0FD33DE6-745B-40AF-A117-1143249D8C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2efb7b91a99bf82ca0c5183eabf701dd08b3c67","datavalue":{"value":{"entity-type":"item","numeric-id":5786239,"id":"Q5786239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$B2FCF6BF-70B6-4288-A29B-3119D4B34946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e11a83a73bbb691eda6d2e4bbe5b5674c4bfeeb","datavalue":{"value":{"entity-type":"item","numeric-id":804582,"id":"Q804582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$15685DCD-6C4C-4856-82E8-3EFDEF4612D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a50d518c7ebdcd2a7b6df34c5131cae28d2cb7f1","datavalue":{"value":{"entity-type":"item","numeric-id":4317708,"id":"Q4317708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$034C8DE1-1E86-4F96-A7F8-5A2CA0E2A9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37a72b86653ea6f671e19f718376e34fcfd0ccdc","datavalue":{"value":{"entity-type":"item","numeric-id":4230331,"id":"Q4230331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$B0E4036F-7A3E-4CD0-9357-BBC0787ADA88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19089571cb49639a5363a336faf3d1b7d285d09a","datavalue":{"value":{"entity-type":"item","numeric-id":3757930,"id":"Q3757930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$F495E8D8-FE42-48A2-9D55-20288D55315D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2dc51f455e8035861032dfb9491c0817f3e724","datavalue":{"value":{"entity-type":"item","numeric-id":1085168,"id":"Q1085168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$D3E4087E-296E-4975-9555-772CAC1ED2A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36313581e6a77d3533a1cd4630fd340bdc11d5ec","datavalue":{"value":{"entity-type":"item","numeric-id":1121926,"id":"Q1121926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$8D81C096-86E4-4E97-B239-D459F27A930C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5065532e34698e0932c1befbffc73b0553719e","datavalue":{"value":{"entity-type":"item","numeric-id":3138887,"id":"Q3138887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$B377D5FC-155E-42B3-A16C-9C9C24477E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f353d3135d977d9eac9a5a76bb0234557168c639","datavalue":{"value":{"entity-type":"item","numeric-id":5804714,"id":"Q5804714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$1FCDA61A-0570-40A3-9E4B-10C0B6253E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d990a995876f36f7ec1a091c259d6d4e2b928d58","datavalue":{"value":{"entity-type":"item","numeric-id":5724435,"id":"Q5724435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$5AC8C918-A96B-456A-BCDE-AEDB43631A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7128b1d457315398d0a5345b19843b0199e890a1","datavalue":{"value":{"entity-type":"item","numeric-id":2645092,"id":"Q2645092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1355197$18E69C04-C69A-45B6-9861-3A0D0EF17D43","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0df7bb2fe2c0c39a6a93e6bec9b9815420389129","datavalue":{"value":{"entity-type":"item","numeric-id":5939541,"id":"Q5939541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2a2d67e8e6dc7b96685a526bd4d687a9a9d90f8","datavalue":{"value":{"amount":"+0.8771010041236877","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":"Q1355197$86E9A3D8-F09E-494E-9412-92E3A1A703C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffde8b505d8cb9d1ba478157470ee568bc401a74","datavalue":{"value":{"entity-type":"item","numeric-id":4501699,"id":"Q4501699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f5dc11174f188450488d5eae6b2739f30d83d10","datavalue":{"value":{"amount":"+0.8760150671005249","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":"Q1355197$E4857F45-CD7B-496C-BE07-3B0DC0C2EC3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0b0919d5f8d693458ef2cc590a1cee29cd82caf","datavalue":{"value":{"entity-type":"item","numeric-id":3138887,"id":"Q3138887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37dbfd3bc513473d87deb61de1cd92179483b2b6","datavalue":{"value":{"amount":"+0.8753963708877563","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":"Q1355197$CC4A684C-0100-4AAE-9BD7-EFF68B6BB446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77b6f888b8724a04e3eb3a725342c5a7a44f5ebd","datavalue":{"value":{"entity-type":"item","numeric-id":804582,"id":"Q804582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3529f865b3e6010a3ce45d54b58585b84aea4f64","datavalue":{"value":{"amount":"+0.8572214841842651","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":"Q1355197$D3BDC873-5A51-4A08-B845-6B39DE3445A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Grid embedding of 4-connected plane graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Grid_embedding_of_4-connected_plane_graphs"}}}}}