{"entities":{"Q1640218":{"pageid":1650959,"ns":120,"title":"Item:Q1640218","lastrevid":68237949,"modified":"2026-04-12T22:21:34Z","type":"item","id":"Q1640218","labels":{"en":{"language":"en","value":"The complexity of computing the cylindrical and the \\(t\\)-circle crossing number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6888452"}},"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":"Q1640218$98EF05A2-4CFA-4E6B-A3EB-4C1311C576BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1171538bbd467fcc1e06254e53d11a8f3ebcbefc","datavalue":{"value":{"text":"The complexity of computing the cylindrical and the \\(t\\)-circle crossing number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1640218$69DF5D6C-01E7-43F6-95A1-C5DE51F98581","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3267e65660815fbbdcf09ef015629d1e9afc7a32","datavalue":{"value":"1388.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$62A35211-8692-4E15-AFD2-BAA35EE393AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"553c2bfbd794127690c2a5a9981f9498774e3e08","datavalue":{"value":{"entity-type":"item","numeric-id":1616236,"id":"Q1616236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$A6669E49-A72D-4178-BD10-6A5CE21D4531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ee469e1302d7edf2aee23fee749efd94698cd7e","datavalue":{"value":{"entity-type":"item","numeric-id":899711,"id":"Q899711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$C03CC5B2-488B-40B9-8BFB-8F61B5284FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06ea670aef2863937cc4159d34925987bca83f96","datavalue":{"value":{"entity-type":"item","numeric-id":463034,"id":"Q463034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$CE5660BB-0D19-49A5-A155-82DABDB8E394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"12db1d501dd7c7aeafeb4b9c28e4b40e345936e4","datavalue":{"value":{"entity-type":"item","numeric-id":1640217,"id":"Q1640217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$56FAF750-DA16-4E3D-9234-253B44412B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"47cc4a44211765edd0e02c4651da2bcaf936b4ec","datavalue":{"value":{"entity-type":"item","numeric-id":463035,"id":"Q463035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$24EE4559-8BF2-40B8-A4C0-BAA2684DEF8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$D7D07D1E-182B-4F5B-8418-86CDE28F4245","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b559bb800700d5ba2a45f57085de6ba33131f78","datavalue":{"value":{"time":"+2018-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1640218$4E767FA2-7551-481C-BBEC-8F1D68D031E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa58f3f22b53074093a3de0b4df6828b3d45e1bc","datavalue":{"value":"https://arxiv.org/abs/1708.01942","type":"string"},"datatype":"url"},"type":"statement","id":"Q1640218$FA48CA6A-2917-48B6-8909-3973F6D77351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"27d2e7dc526de089362f7a757d7b87a54f869e50","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p43","type":"string"},"datatype":"url"},"type":"statement","id":"Q1640218$D327708F-C7A3-4EFF-AE56-20A0623AC7FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ca7514194beb8e21f8a0db4c490649ef9649c0b","datavalue":{"value":"Summary: A plane drawing of a graph is \\textit{cylindrical} if there exist two concentric circles that contain all the vertices of the graph, and no edge intersects (other than at its endpoints) any of these circles. The cylindrical crossing number of a graph \\(G\\) is the minimum number of crossings in a cylindrical drawing of \\(G\\). In his influential survey on the variants of the definition of the crossing number of a graph, \\textit{M. Schaefer} [Electron. J. Comb. DS21, 90 p. (2013; Zbl 1267.05180)] lists the complexity of computing the cylindrical crossing number of a graph as an open question. In this paper, we prove that the problem of deciding whether a given graph admits a cylindrical embedding is NP-complete, and as a consequence we show that the \\(t\\)-cylindrical crossing number problem is also NP-complete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number, namely the \\(t\\)-crossing number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640218$70F749C7-4C53-41AB-A92D-A9B86C20F235","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$D76D8C9C-9097-4FD4-A548-5A5A4D1B7E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$7C68DD71-C3D6-4A52-AEF7-C7CA69144CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$369751FD-51EB-4B7A-892A-A83F9E526676","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb9695c4112d3d12d073c1a2b92ec36b0b7f3266","datavalue":{"value":"6888452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$B9B30E28-F057-4BF8-9453-5E6351CD5CBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c8042189cd9e027706f4fbbc4806b7b475b461d","datavalue":{"value":"cylindrical crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640218$7A52BBAC-8B96-4B86-90F3-8EB37C7FE5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb6b9d70fed8b64a467385fdad2e25b7c4b6bf3b","datavalue":{"value":"book crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640218$F8926D93-7A5C-4C61-9415-015B6D648FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7afb1cc6affdfc407791f169252580bfa28d052d","datavalue":{"value":"\\(t\\)-circle crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640218$0BB448AA-1C64-4C6C-AA67-B6CF5A904FEA","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":"Q1640218$AE61F256-7B54-4675-A5A7-68ACEB3D41B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b37a7540680b371748dcad2451a3c7cc561107d6","datavalue":{"value":{"entity-type":"item","numeric-id":2514231,"id":"Q2514231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$D723FCC3-894D-478D-867F-6C6E7A1E7258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"521934600edf7fa1e3ce65aa598b8d25357b50c1","datavalue":{"value":{"entity-type":"item","numeric-id":2865048,"id":"Q2865048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$2E3EB1EB-06BB-40EB-BCF9-7374D75C4B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3364dcb85ba1ac6f7c5d6d26ab00cc516d9da46","datavalue":{"value":{"entity-type":"item","numeric-id":2936927,"id":"Q2936927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$9D6BBF3C-C249-420D-8CB0-7C03AF9143F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3c9fb0ec2c996e4ccdde674bb368938bd0dfcc","datavalue":{"value":{"entity-type":"item","numeric-id":2431395,"id":"Q2431395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$1758CD3F-2565-4B73-9BF2-121D88A026E8","rank":"normal"},{"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":"Q1640218$9509136A-02D5-4476-AED3-D918C81120E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec11463fe2d60a303760ce9865ecede41d671bcb","datavalue":{"value":{"entity-type":"item","numeric-id":1850624,"id":"Q1850624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$E490EC45-A4DE-4F30-8F0D-AFD0B4CB95AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b602d01a898344ce4e168ea2188a5d94cd04e17","datavalue":{"value":{"entity-type":"item","numeric-id":4727445,"id":"Q4727445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$8FA8CD11-F5C5-422C-8EE7-51CCCE6CFAD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20b81d741c94e4f27386713117493d5de17f931c","datavalue":{"value":{"entity-type":"item","numeric-id":5728983,"id":"Q5728983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$8A30A33A-9D86-42A2-832B-255E472F8C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff105bf57bc350e4ab251e3c7429544479b8c3b1","datavalue":{"value":{"entity-type":"item","numeric-id":1953539,"id":"Q1953539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640218$787823D1-56B0-4505-AB86-F8457393FE5E","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":"Q1640218$B74450BA-3AD7-4FDB-9436-25D032910D05","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ee29d943382ad4a9b1ee2935415cb6cc89cecc0a","datavalue":{"value":"bafkreidhlhqvk7agp5gd2bpvm3nnm5r3ior7gnvcn4lo7bm5ci2eudjxne","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640218$8C484B92-7255-49EB-AA22-03F12A4D6A56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"314baa9eb295d607c17c27a682163b79422fca14","datavalue":{"value":{"entity-type":"item","numeric-id":5311149,"id":"Q5311149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f6cab852bf0b345a0fbce799e0bc8a11c81408c","datavalue":{"value":{"amount":"+0.7734537124633789","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":"Q1640218$6C42721C-C1BC-43FB-89C4-2950DDDC1C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f635bd87769c47ce9d82392c62a4a5e5524f1b19","datavalue":{"value":{"entity-type":"item","numeric-id":2496198,"id":"Q2496198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d2e4595e43ee6ac05b126b835928918e84405a5","datavalue":{"value":{"amount":"+0.7729384899139404","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":"Q1640218$07933C5D-E832-4830-AAE2-A8359A03D309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5af89211a79c5e6a5211bdbae33ec5c05f0a9541","datavalue":{"value":{"entity-type":"item","numeric-id":2308490,"id":"Q2308490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a1a9c006f3136a34fcf881f4a02ccf262a2f388","datavalue":{"value":{"amount":"+0.7716155648231506","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":"Q1640218$4A898A47-48D9-4348-8CA1-540C20B6AF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7a14db6ceeb9f7e9ba27eaf65a835bed81ac136","datavalue":{"value":{"entity-type":"item","numeric-id":5452204,"id":"Q5452204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88e7d2eb5d18698bec24a84afa4b1a4c5ddf97bb","datavalue":{"value":{"amount":"+0.7633283734321594","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":"Q1640218$08B59503-28B6-4C9E-9D98-73C7B0D9B3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0da3493b58b6517ba9c4334d2884653ed0b3c21d","datavalue":{"value":{"entity-type":"item","numeric-id":548653,"id":"Q548653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e4459557fd5aa8d109e8c06560b742c27d909e5","datavalue":{"value":{"amount":"+0.7630066275596619","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":"Q1640218$191D3535-F8B6-4D7E-9922-7D519EDD6CDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of computing the cylindrical and the \\(t\\)-circle crossing number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_computing_the_cylindrical_and_the_%5C(t%5C)-circle_crossing_number_of_a_graph"}}}}}