{"entities":{"Q1328384":{"pageid":1339134,"ns":120,"title":"Item:Q1328384","lastrevid":67180143,"modified":"2026-04-12T15:50:20Z","type":"item","id":"Q1328384","labels":{"en":{"language":"en","value":"Grid minors of graphs on the torus"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 599860"}},"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":"Q1328384$C85AF3C7-47AE-4E24-AD9E-8817E1F35F44","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"24d1448acd2d9c3347595f18d5a45a785feabf4a","datavalue":{"value":{"text":"Grid minors of graphs on the torus","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1328384$27F7AF27-DF33-4CDC-AF45-A256E8388930","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64dd3098dbcfe67280c219775d330a9ecb641ea9","datavalue":{"value":"0809.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$21FF137C-6622-4CC3-9F37-A024C6DEF3C7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e41d7e0bcbb20557f3edf0a929e124ff17cdaf31","datavalue":{"value":{"entity-type":"item","numeric-id":1328383,"id":"Q1328383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328384$E4F83012-40E9-4D26-AB8D-5F4AF0185E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbf8d5cbd9ece6bead4e0fa5d545881c7f63f46","datavalue":{"value":{"entity-type":"item","numeric-id":6481473,"id":"Q6481473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328384$D500186E-E255-49B4-8B41-2FD9B14D408A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328384$6C3F75EB-71AE-41E2-B04A-DDA9590B626A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"12c17d7316137b5457243cfe10f00c4bb5a56573","datavalue":{"value":{"time":"+1994-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1328384$467DE054-33CA-4C7F-8239-88DE074D8FC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44ed1a5ca445561a22563303994f3118d3ee9402","datavalue":{"value":"The face-width of a graph embedded on the torus is the smallest \\(n\\) such that there is a noncontractible cycle on the torus which intersects the graph in exactly \\(n\\) points. For example, the product of two \\(n\\)-cycles \\(C_ n\\times C_ n\\) embeds on the torus with face-width \\(n\\); this embedding is called the toroidal \\(n\\)-grid. A graph \\(H\\) is a minor of \\(G\\) if we can create \\(H\\) from \\(G\\) by a sequence of edge deletions and edge contractions.   The authors show that any graph embedded on the torus with face-width \\(r\\geq 5\\) contains the toroidal \\(\\lfloor 2r/3 \\rfloor\\)-grid as a minor. Moreover, the value \\(\\lfloor 2r/3\\rfloor\\) is the best possible. An equivalent form of the result is that every toroidal graph with face- width at least \\(\\lceil 3k/2\\rceil\\) contains a toroidal \\(k\\)-grid as a minor.   The proof proceeds by taking an embedded toroidal graph and constructing an associated planar polygon with integer coordinates which is symmetric about the origin. The grid minor corresponds to the existence of two linearly independent integer vectors of a certain length.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$4018E755-67E4-4E31-ACEA-546337808929","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$E955C2E3-BB67-47CB-BC0D-26519E8C0CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$E4A49197-3C88-4DD2-9EBF-973E75DE17A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b01ad1b16eab7f86b2e20d189e8d8d07f644af25","datavalue":{"value":"52B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$DFD6D2DE-E92A-4593-9E53-47849DD46A27","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15611d315777ff72a49256ed8ce0c6a387f225e8","datavalue":{"value":"599860","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$3C47C0DA-60CB-4351-A076-4675EDCA4144","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24ee27feab6365a1168b8c97c8d165cd061c4be0","datavalue":{"value":"face-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$7209CA43-D85E-46FC-B18D-B1084F209205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"792cfb8f1604e9c7b9163c7b6a704699a9fe20ce","datavalue":{"value":"torus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$F8A58E88-6D61-4910-9987-2B3DC597CA13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e653f9c03c808dfcd66f771fa670bc9f2783555","datavalue":{"value":"noncontractible cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$D1D8C4F7-922F-46A3-9850-C8766AE4662F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6d9ec77b0669b77734b6831d672122e99e5245c","datavalue":{"value":"minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$17635DFA-3634-44FE-ADA6-6D3E0FD59756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06d9d0201c7071a9c83772de616d279d2cf4cdba","datavalue":{"value":"toroidal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$1451835D-A51C-4C46-9091-B9E1C1DD16CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eff1fb29fc2d064e02046d971bf921f74d1c775","datavalue":{"value":"planar polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328384$824CF0AA-EA37-4CCE-8F9A-1C8C0CA01DFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328384$11CD459D-6B18-44A4-9639-52F49D61E362","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":"Q1328384$54BEA9EB-CB9B-4BEC-A170-29F945333B11","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"618e838845118a6e6f5238f4582445211fdcc83d","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1029","type":"string"},"datatype":"url"},"type":"statement","id":"Q1328384$C0E9082C-11AE-400D-B30E-21B94B558666","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"30bafb5467e5be2f01ea703b27ccedf214b9398a","datavalue":{"value":"W1970011611","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$4100A6DA-A278-431A-A3AD-760220AEC474","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"375418987416a21cd84287b001b4b4062f3b658e","datavalue":{"value":"10.1006/JCTB.1994.1029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328384$ECAAB4DB-9D59-43DB-B856-F71F82BE639F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a70f6301e5c7f759e976f7b46b1cf8e58d1129bf","datavalue":{"value":{"entity-type":"item","numeric-id":1333341,"id":"Q1333341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cba196230324c742aeb4315183926e110e23e08","datavalue":{"value":{"amount":"+0.8335123658180237","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":"Q1328384$413683D8-295B-42B0-B816-109DDF54F3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b85c2815f98e5d2891ea6148c76d1b1e3e5cc3d7","datavalue":{"value":{"entity-type":"item","numeric-id":949776,"id":"Q949776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b203cea81a9971b5107f72541c0ed6da633702","datavalue":{"value":{"amount":"+0.8295689225196838","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":"Q1328384$A832646E-A190-4F4A-84C8-18139242FAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e23bd023fc3f80f13af6de2fb087d85655e98e6","datavalue":{"value":{"entity-type":"item","numeric-id":2284733,"id":"Q2284733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c5581f26b5ea379be8b6080f9e4786bbd791d0e","datavalue":{"value":{"amount":"+0.8076855540275574","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":"Q1328384$3DC487CD-28B4-4596-A5F3-1EB67B051B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc8cbe07bd1c8195839700ae2e28f6c9010a460e","datavalue":{"value":{"entity-type":"item","numeric-id":885291,"id":"Q885291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98d0b5c6ed5af9f36fb141dd861f376c3e19e56a","datavalue":{"value":{"amount":"+0.7978577613830566","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":"Q1328384$8CF5E375-E882-4230-92D3-C96A4499373B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f68439d46a537257fe7530d90aa0c0f3bf19fff","datavalue":{"value":{"entity-type":"item","numeric-id":1883290,"id":"Q1883290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"118bc1e555f3a5080e081fb9fa6af90cf964f066","datavalue":{"value":{"amount":"+0.7867440581321716","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":"Q1328384$C5F2D588-F4E8-48E8-A786-1283D846048E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Grid minors of graphs on the torus","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Grid_minors_of_graphs_on_the_torus"}}}}}