{"entities":{"Q5939541":{"pageid":8116343,"ns":120,"title":"Item:Q5939541","lastrevid":47649778,"modified":"2026-01-02T07:40:50Z","type":"item","id":"Q5939541","labels":{"en":{"language":"en","value":"Grid drawings of 4-connected plane graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1626139"}},"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":"Q5939541$F5798D95-69ED-4D3F-A4AC-84270F0306AB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b3bbfd1a3c3b01104995c0db224af75250f283a7","datavalue":{"value":{"text":"Grid drawings of 4-connected plane graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5939541$2394FB6E-C22A-4F10-8B86-CDFEB00494A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dacb4ad9692ffe8d79a96fd2df8f82a72655357c","datavalue":{"value":"0978.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$A0F49A1E-B687-4438-97FA-C09CF4E115C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"16c0d876b0993ba3c076d0637b1a6b3d721281ae","datavalue":{"value":{"entity-type":"item","numeric-id":1000922,"id":"Q1000922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939541$88E42611-86B9-433D-8429-264069833CC2","rank":"normal"},{"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":"Q5939541$5D2D3CFB-3203-434D-A90D-E39D06ABB0D2","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":"Q5939541$0375E5B1-B706-493E-BC64-2E40F6F6A427","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":"Q5939541$7EC04C78-7A2C-4A62-A0A4-D1EBF65FF2C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"da1e102b79cffd268b6f68feaae2005a6fba4d8e","datavalue":{"value":{"time":"+2002-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5939541$BB7B391E-7A3E-43CF-8E8C-DC8C8D7B9891","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"753c390cad35ffd984818aa65ed4ddb8d148cff5","datavalue":{"value":"A grid drawing of a plane graph \\(G\\) on a \\(w\\times h\\) grid is a drawing of \\(G\\) in the plane in which the vertices are put on grid points with integer coordinates \\((x,y)\\), \\(0\\leq x\\leq w\\), \\(0\\leq y\\leq h\\) and the edges are drawn as straight line segments intersecting only at common endpoints. The authors present a linear-time algorithm which finds a grid drawing of a given 4-connected plane graph of order \\(n\\) which has at least four vertices on the outer face on a \\((\\lceil n/2\\rceil-1)\\times\\lfloor n/2\\rfloor\\) grid. This improves a previous result of \\textit{X.~He} [Discrete Comput. Geom. 17, No. 3, 339-358 (1997; Zbl 0877.05014)] whose algorithm provides a drawing on a \\(w\\times h\\) grid, \\(w\\leq(n+3)/2\\), \\(h\\leq 2(n-1)/3\\) and \\(w+h\\leq n\\). The construction is based on the 4-canonical ordering introduced by \\textit{G.~Kant} and \\textit{X.~He} [Theor. Comput. Sci. 172, No. 1-2, 175-193 (1997; Zbl 0903.68137)] and uses a simple idea of dividing a given plane graph into two subgraphs, drawing each of them in an isosceles right-angled triangle and combining both drawings. It is also shown that the bounds are the best possible by exposing an infinite class of 4-connected plane graphs any grid drawing of which requires a grid of size at least \\((\\lceil n/2\\rceil-1)\\times\\lfloor n/2\\rfloor\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939541$A20B14A9-0EF4-420C-98EF-1CC946303866","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939541$D46AF8C7-F4B7-446C-B40F-91D2D838AD0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$9F58C1AB-FA82-4FC7-BE05-6556E7FEAC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$B8EE2DE9-1A92-479D-BA90-ED09815A2A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$E462AD5B-5219-4AD4-A311-C54E67F5294F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$6E52ED83-1938-4080-BA2C-6D8988D90B2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e4f908dc13e2499988011dad36a3207aad19d93","datavalue":{"value":"1626139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$F4254E55-356B-4419-8D36-9347E140F6F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939541$DAE18CE9-648C-4DFB-9DE2-D0A5DAFBAB4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dc9ebb9f5d29814dd7a1732545218d019990bea","datavalue":{"value":"grid drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939541$F30D27F5-BFE8-49C0-89F5-8134682D9D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2bcb2b02b6fc9422e1421e60515a2f96826dde0","datavalue":{"value":"4-connected plane graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939541$910BD66A-FBD4-455A-9388-2F275E2B2E2D","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":"Q5939541$1B030D78-088A-4954-9A1F-35213FFE304F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db42824e94e1d577e539dca25dddd6f11d134615","datavalue":{"value":"https://doi.org/10.1007/s00454-001-0004-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5939541$B0044723-D185-4778-B699-9FDE1C0A3EDC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ae8512c9d099499e734575818a1c89a0b94a718","datavalue":{"value":"W2013871179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$3B4B6E01-3208-4399-A539-ABA41EDC231B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d748e7545fc1458c358ff9ab1d058ed6636d7b5c","datavalue":{"value":"10.1007/S00454-001-0004-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939541$B58A0AA0-0F42-4037-8FC8-B9736D020EED","rank":"normal"}],"P1643":[{"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":"271f9465e63d82ad6a0cd47c7fb58d44db3263ea","datavalue":{"value":{"amount":"+0.9654318690299988","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":"Q5939541$97644F97-A399-41D0-AD22-79CEA7D3DCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32f80be0d1b64d362a85d927d72f452ca4400fc2","datavalue":{"value":{"entity-type":"item","numeric-id":4472498,"id":"Q4472498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03651e639ddcee73d636052a2bf17407dcb93e32","datavalue":{"value":{"amount":"+0.9173980355262756","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":"Q5939541$0094F0B8-A5FB-4F1B-94C5-D267E1C895B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"338c8d2b13823b9d37427ab45b6ec62c0c5910d4","datavalue":{"value":{"entity-type":"item","numeric-id":5493893,"id":"Q5493893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e82e4632baa1cb5c2cb5a520011c634d54c53d41","datavalue":{"value":{"amount":"+0.9113190174102784","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":"Q5939541$A06DD7BA-F404-4345-BA33-39495D80D1E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33bd0bd5ee563a82db04dbf5177ed6f467e5c42d","datavalue":{"value":{"entity-type":"item","numeric-id":1355197,"id":"Q1355197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7ea8b88aac39a864581757299417d9d6d85eb9a","datavalue":{"value":{"amount":"+0.8768925070762634","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":"Q5939541$460B6312-A402-4806-B310-4E6D0BFA73CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd64dc4c21fc09c568db59a30f070f370cba1282","datavalue":{"value":{"entity-type":"item","numeric-id":1920418,"id":"Q1920418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7ea8b88aac39a864581757299417d9d6d85eb9a","datavalue":{"value":{"amount":"+0.8768925070762634","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":"Q5939541$AE7482C2-AADB-4E6B-B4DF-54F91F331A68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5939541","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5939541"}}}}}