{"entities":{"Q1880792":{"pageid":1891534,"ns":120,"title":"Item:Q1880792","lastrevid":48353422,"modified":"2026-01-04T11:18:09Z","type":"item","id":"Q1880792","labels":{"en":{"language":"en","value":"Crossing number, pair-crossing number, and expansion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2104551"}},"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":"Q1880792$7D75C5C6-0A3A-4D30-BCA4-E038A187A883","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2de515e8768b896344f20f05fbac90f1b08f83b","datavalue":{"value":{"text":"Crossing number, pair-crossing number, and expansion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1880792$0C0A2D91-4B68-41D0-90DF-171C4F90CFCF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24b95e7c9875fe342877cadd06ec9dd5a89e7126","datavalue":{"value":"1051.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880792$AAA7F014-5B73-41CA-B352-D4CC14A3F394","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa63f642e27dbdecb94bd4e745870cb22f9dbc7d","datavalue":{"value":{"entity-type":"item","numeric-id":372973,"id":"Q372973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$9E3AFD4D-9254-49EB-9EB0-1EB49C5863A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5205659b4c2831752a8f8604dc5b3ce7b9439fa","datavalue":{"value":{"entity-type":"item","numeric-id":818688,"id":"Q818688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$100DCB23-D3C9-416C-8D8D-CFB799395D3D","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":"Q1880792$06A7DDB0-A2C0-434C-BB4B-C1B7DB20CF71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"221b8cdf103f88fa9a30fbc31f4b00396bad2596","datavalue":{"value":{"time":"+2004-10-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1880792$DC705A0D-0D6C-40EA-8BD8-2672D7417AC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9cc80e8e73bacc79968296bf671d9680ecfac730","datavalue":{"value":"The crossing number \\(\\text{cr}(G)\\) of a graph \\(G\\) is the minimum possible number of edge crossings in a drawing of \\(G\\) in the plane, and the pair-crossing number \\( \\text{pcr}(G)\\) of a graph \\(G\\) is smallest number of pairs of crossing edges in any drawing of \\(G\\) in the plane. It is a major problem in graph drawing if always \\(\\text{cr}(G)=\\text{pcr}(G)\\) or not. (This problem was independently raised by Mohar, and independently Pach and T\u00f3th.) There is a very important lower bound for the crossing number in terms of bisection width: \\(\\text{cr}(G)=\\Omega(b^2(G))-\\sum_v d^2(v)\\). The paper finds an analogue of this lower bound for the pair-crossing number: \\(\\text{pcr}(G)=\\Omega(b^2(G)/\\log^2 n)-\\sum_v d^2(v)\\). (In the formulae above, graph \\(G\\) has \\(n\\) vertices, \\(b(G)\\) denotes the bisection width of \\(G\\), and \\(d(v)\\) denotes the degree of vertex \\(v\\).) The main result of the paper is \\(\\text{cr}(G)=O(\\log^3 n(\\text{pcr}(G)+\\sum_v d^2(v)))\\), which is a substantial progress. The paper also shows that graphs with large crossing number have small non-planar subgraphs. The proofs use expansion and concurrent multicommodity flows.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$0BDC0F90-991E-4CCB-AF15-342010DBCC93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880792$B11B6A8D-D856-453A-AEC4-718012A6FBB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae60aa985c627941ef1540bf1b099d62a081d4e7","datavalue":{"value":"2104551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880792$649F85A3-D0AD-409D-AD0C-8637273CDF4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$BA11C4C1-DCFC-4C53-853C-05BF66CAE736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0bf0dbd5dd844463866c53b1b3f022210f94a95","datavalue":{"value":"crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$8E442B5C-3A5E-4C01-8FFE-B880BCF74CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50c99a8339086440c9c7f8cede005962ac6d85a8","datavalue":{"value":"pair-crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$86D75012-092F-419F-9721-3F7200857FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a56e5793ea33870a204239ad40fe7f02bf24fac2","datavalue":{"value":"expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$77C11D4E-535B-4FD9-8546-47A6A6A1F142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"796bd73e2d9a029dbf6d853444eccd8dfae9ec49","datavalue":{"value":"concurrent multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880792$6BA3FDA2-1960-4549-BC99-0F8AFE0034FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"706e08216f8d7e32a9bfdcc84aeeba4ad0f22d8d","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$4462F7BF-311B-4D86-B822-D439FF3AD238","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":"Q1880792$BF0D9662-96DF-45E0-9F0E-8A2E0495131F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"55f9da7fe8529747e9f8e7b831416c46ed4704de","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2003.09.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1880792$6603E71C-5C77-45A6-BF94-74B77CDE4C16","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"59f3bcd6b995045670f972e9ded1975b84e38e1f","datavalue":{"value":"W2000052110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880792$FCEFECE6-9EAF-4812-ADD6-5A81C00F5385","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e7cafa589be10b4e1724da41974b4ce96da0028","datavalue":{"value":{"entity-type":"item","numeric-id":3967549,"id":"Q3967549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$E4E068D9-2B5E-4DEA-B8F5-273BEA91657C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad6f96cf3556c62b2e9742e2f30fb947f47dc362","datavalue":{"value":{"entity-type":"item","numeric-id":5901073,"id":"Q5901073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$D83B24E0-5026-462F-B868-D4C4EC6C58E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d823bde0afa959f545aa85998f405220b941317","datavalue":{"value":{"entity-type":"item","numeric-id":796306,"id":"Q796306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$8CEA0664-C1B0-46CB-9E81-C649B8006740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"219ee0be5142918ed954a78a8704581cbc4105e7","datavalue":{"value":{"entity-type":"item","numeric-id":4706191,"id":"Q4706191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$9047A060-C8D3-40BD-9883-28DE6613EA2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3e8bdd2c894b65a316790f02dd9ea490c60bc9a","datavalue":{"value":{"entity-type":"item","numeric-id":4828931,"id":"Q4828931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$464B9C4A-CC11-4BCE-9645-3150F97CF06E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e25641d7676eb871c7c60c600ae48bd5882ba234","datavalue":{"value":{"entity-type":"item","numeric-id":3950484,"id":"Q3950484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$B79B1C68-5E5A-426A-8FA8-2A7C2F5343B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0975cfaaab9f60b666ac4d872784d890adabb351","datavalue":{"value":{"entity-type":"item","numeric-id":3158558,"id":"Q3158558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$7D2D8EF1-EBF8-435F-8E84-F691DCFF4CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$EF58DB52-EFC6-415A-8283-EB1EFF2910E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b15bc2894d3c3113990f2df75e823aff547e107","datavalue":{"value":{"entity-type":"item","numeric-id":1920423,"id":"Q1920423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$051FC957-0888-4100-B057-13D66995BF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2881998cbc02ae16f87883cd190fa272528eba58","datavalue":{"value":{"entity-type":"item","numeric-id":4484691,"id":"Q4484691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$EFE05163-DC2D-42C9-A6AC-87D636381E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d7d73af8b98c97add638c2285b256b3d9ed5cd7","datavalue":{"value":{"entity-type":"item","numeric-id":1850498,"id":"Q1850498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$93C98A9E-DD05-45AD-97A5-14623A5CFEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4e8dc073a2888e089c93d173f863d5b7cc1da1","datavalue":{"value":{"entity-type":"item","numeric-id":5491727,"id":"Q5491727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$F4C2B6F4-5EF4-40C4-9955-D343FA6E57B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0611c8fede42ac100885c81ef1a90e51ba7e3b3","datavalue":{"value":{"entity-type":"item","numeric-id":1106724,"id":"Q1106724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$D8F9CD12-3EE4-4CCD-948B-117531447209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fc854b784edf07c2a27fd4a1924849326b792d9","datavalue":{"value":{"entity-type":"item","numeric-id":3082956,"id":"Q3082956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$8A42C2AF-4A8D-4611-8147-4BA6F0798363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e8f6329d24b080f58b7a8c57806f2a8b324b94","datavalue":{"value":{"entity-type":"item","numeric-id":4352316,"id":"Q4352316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$9D3D4A31-E7A6-47BE-BBD5-4895390C44ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95a0f2ba11d6ed21e1352d453aed82641fc6a4d7","datavalue":{"value":{"entity-type":"item","numeric-id":4879178,"id":"Q4879178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$3156CD94-E72A-4350-84EA-9975D26008A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa725e3a14983c91192dfc26f8425a366cd02a6d","datavalue":{"value":{"entity-type":"item","numeric-id":4798172,"id":"Q4798172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$95E53297-2CE1-4F30-AB1B-D85B4E0EDAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7d27256273a4c4755e088ab2ba2ec6593e490dd","datavalue":{"value":{"entity-type":"item","numeric-id":4322467,"id":"Q4322467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$35382208-B31D-4AD0-9B96-BC20A6E483F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44cdf73b7ceeb536827d8a4482ccc895b3f6424e","datavalue":{"value":{"entity-type":"item","numeric-id":5578799,"id":"Q5578799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880792$17E19573-A68D-45E3-B6F2-82D69CA2C3DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cff3fca93f28b6eaf41158986fb8a5790fe0e1e5","datavalue":{"value":"10.1016/J.JCTB.2003.09.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880792$367AE0D9-D194-40AE-AEBE-E8FE521D11FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ad107261044e9cacb8f86a4df07be0911e24251","datavalue":{"value":{"entity-type":"item","numeric-id":2847927,"id":"Q2847927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b59594b0e9353d70dce36f624b5d0bf31ce6bf33","datavalue":{"value":{"amount":"+0.8645185232162476","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":"Q1880792$ED140A22-D74F-486A-9130-FFE0862892EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca823c4e0709835a2759839984ec90d4882f85b7","datavalue":{"value":{"entity-type":"item","numeric-id":2936928,"id":"Q2936928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48645eb983fbdd7bc6b181bf9bf4cefbc6b2b15c","datavalue":{"value":{"amount":"+0.8379216194152832","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":"Q1880792$8E8C139E-D1E8-4611-9B58-4F1A79978EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"598a177a2f55432a9d190d0efc9e65b24fdefbc8","datavalue":{"value":{"entity-type":"item","numeric-id":3043708,"id":"Q3043708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5de12d25f2cf74b5d0ca6fe77c695d84e4adbc2","datavalue":{"value":{"amount":"+0.8373531699180603","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":"Q1880792$3CC9DF1B-217C-48F8-9A03-51E79C15EFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e02fe0221ee91a202353e78eb158a7c3dcee4024","datavalue":{"value":{"entity-type":"item","numeric-id":4679068,"id":"Q4679068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"147547ded9c55ce5158b70780f080cd0da302f81","datavalue":{"value":{"amount":"+0.8296667337417603","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":"Q1880792$ABE51927-823B-49CB-B379-3F10E90FEE0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27e77b6cc3e001dd6a3a22eb0c55063f1a684212","datavalue":{"value":{"entity-type":"item","numeric-id":938304,"id":"Q938304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fbbe554732df4af0b26f397e0ac0aa5a5906c3c","datavalue":{"value":{"amount":"+0.8273744583129883","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":"Q1880792$6ABD9861-ECC1-49F8-B9D1-9C0F45FD9C05","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1880792","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1880792"}}}}}