{"entities":{"Q1770400":{"pageid":1781142,"ns":120,"title":"Item:Q1770400","lastrevid":72502458,"modified":"2026-04-14T05:21:41Z","type":"item","id":"Q1770400","labels":{"en":{"language":"en","value":"On the one-sided crossing minimization in a bipartite graph with large degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2153195"}},"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":"Q1770400$9193364A-2266-4A6C-B655-9C3EBB23C3A0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8285c72b80d55757dab6f9647408cf8d5212170a","datavalue":{"value":{"text":"On the one-sided crossing minimization in a bipartite graph with large degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1770400$F6F08815-B09C-4E83-BE3F-57A389E72A5E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18092c6cd61d9e4763385164857cfc61115fbf87","datavalue":{"value":"1142.68461","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$7CD37B47-1336-4B98-9EC1-17BF125CEA34","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60eb2392c3cbb67419a7505eb4d7770437782b61","datavalue":{"value":{"entity-type":"item","numeric-id":187130,"id":"Q187130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$6E9186AD-A953-4929-BBC6-9E5ED5EF877C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$0AF2421C-E074-40A1-8830-AFC92AB16C67","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1934d792c26a5fadc4b54d2e40cc5c88366797ca","datavalue":{"value":{"time":"+2005-04-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1770400$D8769459-51E3-48A8-87FF-B4D3E5A90965","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"636cc4c5669656b44a8a06e6de8c332a5110f3c5","datavalue":{"value":"Given a bipartite graph \\(G=(V,W,E)\\), a 2-layered drawing consists of placing nodes in the first node set \\(V\\) on a straight line \\(L_1\\) and placing nodes in the second node set \\(W\\) on a parallel line \\(L_2\\). For a given ordering of nodes in \\(W\\) on \\(L_2\\), the one-sided crossing minimization problem asks to find an ordering of nodes in \\(V\\) on \\(L_1\\) so that the number of arc crossings is minimized. A well-known lower bound \\(LB\\) on the minimum number of crossings is obtained by summing up \\(\\min c_{uv},c_{vu}\\) over all node pairs \\((u,v)\\in V\\), where \\(c_{uv}\\) denotes the number of crossings generated by arcs incident to \\(u\\) and \\(v\\) when \\(u\\) precedes \\(v\\) in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most \\((1.2964+12/(\\delta -4))LB\\) if the minimum degree \\(\\delta\\) of a node in \\(V\\) is at least 5.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$5EC9A8AA-0ED3-4918-BF15-2C21B0F45F80","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$AC3736D6-A892-43B4-AFEF-2B8F167FD3F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$C1F3C81D-B627-4AEA-AA41-52A2435945F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$14609E51-7DC4-4EEB-9981-B46A1BDA013D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$C89FB4F4-F8EF-4756-AEAE-60A5CB0860AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$BADC252F-0DDA-46EE-929F-3C36C7EFC70B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$7D806F18-9654-4729-9C07-9F5B2368A782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$40A25B98-697D-4322-A2E5-2AAD97044673","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2895e28bb246563d8d204b94ef3efd3bf11ed476","datavalue":{"value":"2153195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$E34260A5-D00D-4F6D-BADF-59BFD0D2AC73","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88af4e5a05d47825dc6aecd65a3f68a98232d37a","datavalue":{"value":"Approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$DE39B386-97DC-4C16-8017-BB00022E4BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc74a074f89c8860fb7e4c492ab49b3159bf875a","datavalue":{"value":"Bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$CF5C8FC6-3ADE-4B6C-83EE-5E91D908F451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cb41bee26dd88599cb086a8b1e395340fff6a7e","datavalue":{"value":"Edge crossing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$2FB29950-C118-4A5B-AD26-4EF93686A346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4860c3d601841875937ce1d7bfa6d9a60a994a35","datavalue":{"value":"Graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$30FDCFFE-6295-4A48-B690-863518AB0AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ea38922787cfe23b5d1e83598a576cde4ff79d5","datavalue":{"value":"2-layered drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$D5B0A92E-0518-4892-830D-A455A85AF24D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4da94df5926ae722f3f5ef499d18cc349712b321","datavalue":{"value":"Randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770400$DFE533EE-AF53-439A-9812-CA944BB58066","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":"Q1770400$170AA08A-2A9D-478E-BD51-E89431D7497A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1cb1d11433bbd29914c2fcb1344e816b724d327","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.10.042","type":"string"},"datatype":"url"},"type":"statement","id":"Q1770400$A0B5DEF0-844F-4D1C-A9EB-A60FA6DC1020","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"50da564c167fcb69ddd7aaa2f68d7feead52eff4","datavalue":{"value":"W2017361734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$8911C66F-7DEE-4035-8639-2DF0AA864B77","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"625a03d46620a33bee2de786dbc5e81f0c26accc","datavalue":{"value":{"entity-type":"item","numeric-id":3154375,"id":"Q3154375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$3457826E-5409-4B21-9CC6-F620216F41C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97661ce613ddda7344c1a18eadb560d4c2bdbd42","datavalue":{"value":{"entity-type":"item","numeric-id":5896903,"id":"Q5896903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$72180CCD-5AB3-43CA-B14B-67FEBDC593FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b65765fbb4338f3ef58e25d6b51f1b1a626dc407","datavalue":{"value":{"entity-type":"item","numeric-id":4422268,"id":"Q4422268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$782976F8-4380-4447-93B1-920742C08F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d692cc639d3f2222b9333fbaa7484f851254bd2c","datavalue":{"value":{"entity-type":"item","numeric-id":1322570,"id":"Q1322570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$8EA663A1-07D9-406B-9242-30F8CEDEAD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c73ad48d69dfe9d46075a7f82c801990754a4864","datavalue":{"value":{"entity-type":"item","numeric-id":3320398,"id":"Q3320398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$66D3AFC1-EDD5-4BFA-A290-D661D31FCD30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c961616caeda34d6ee5ba4cf37536f389ec2256","datavalue":{"value":{"entity-type":"item","numeric-id":5625198,"id":"Q5625198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$9F115605-8E49-48DE-973F-9FA985B761AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"767fc83d7584ff8cc561702aee08fdfcb268f4f0","datavalue":{"value":{"entity-type":"item","numeric-id":5677508,"id":"Q5677508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$B81299EF-E610-4258-9761-7F8BCF711D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2af3b73b601f1f2e30451090cd8c5f56c8b9fe","datavalue":{"value":{"entity-type":"item","numeric-id":4381060,"id":"Q4381060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$1A4257FC-5C3C-4808-8B4D-708023B0784C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b89c52e8b334c9e4ca2e270b81942028c60f004e","datavalue":{"value":{"entity-type":"item","numeric-id":1853018,"id":"Q1853018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$507573B8-5A0F-4281-BA9C-5C71427BA5BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9868e1feb5f6807c62516ed740c855e2b1119db","datavalue":{"value":{"entity-type":"item","numeric-id":5899817,"id":"Q5899817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$68049BD9-E6A9-4FCB-B5AA-7ECE5560707A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e486f81895a68174927a843cac5cdbd91e7bc7d1","datavalue":{"value":{"entity-type":"item","numeric-id":3043710,"id":"Q3043710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$9FCB9FE0-5979-4195-9569-24E44274163A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b1c975d0abff938e1fd515e5e72fed11564b52","datavalue":{"value":{"entity-type":"item","numeric-id":5896909,"id":"Q5896909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$F6AA7DF5-0FA8-4B6B-A753-D10CC877095C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed279defab1d9e8ae145983da65f20afaeb13973","datavalue":{"value":{"entity-type":"item","numeric-id":2484013,"id":"Q2484013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770400$8FBA52F5-4D2E-4479-9505-24BCA6EB2561","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8954bda727405bd91f1ab5d098c629bd71cf4037","datavalue":{"value":"10.1016/J.TCS.2004.10.042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770400$B321BDAB-CC77-48EE-BBEB-FB062967AA9E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e3d26952b140106b9546202261c70d0d4069d5c","datavalue":{"value":{"entity-type":"item","numeric-id":5896909,"id":"Q5896909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88a79d4240071199029d5ee574187546be3b0cf5","datavalue":{"value":{"amount":"+0.9042407274246216","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":"Q1770400$D7E358F1-E92D-4B15-B9F1-7FD308ED0644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9d82a31449e1f8358a81aaba324c1a0359841cf","datavalue":{"value":{"entity-type":"item","numeric-id":2484013,"id":"Q2484013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9fe80cc3e9e5384d7c48ccb1baddb617647b34e","datavalue":{"value":{"amount":"+0.9040656089782716","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":"Q1770400$8840D848-9EA4-462E-9E84-7FBBBEDF51C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ad8cb4672ea48251e6d807627886a603f0457f7","datavalue":{"value":{"entity-type":"item","numeric-id":1044030,"id":"Q1044030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ff47854b2b286ea915572583521bc60e7503642","datavalue":{"value":{"amount":"+0.8161476254463196","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":"Q1770400$CFF304F8-A9FD-4191-89DD-4AFF8587845F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4187145d48c4a3d6f794b36bde8b267bf5763cc6","datavalue":{"value":{"entity-type":"item","numeric-id":5432313,"id":"Q5432313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79714e1f06f797bb63f06b38e05606ef5bd6750d","datavalue":{"value":{"amount":"+0.8151670098304749","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":"Q1770400$96497496-AF67-4F96-9C9B-11FF99E63E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70bded3860a0d03d79c82681c47944c71eea13b0","datavalue":{"value":{"entity-type":"item","numeric-id":284334,"id":"Q284334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a7b05b5d221371217d616da6e6b9431783ffe01","datavalue":{"value":{"amount":"+0.8001948595046997","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":"Q1770400$FEC5EEFE-4BDF-4CB2-AB01-F2AD0912C932","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the one-sided crossing minimization in a bipartite graph with large degrees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_one-sided_crossing_minimization_in_a_bipartite_graph_with_large_degrees"}}}}}