{"entities":{"Q1684937":{"pageid":1695678,"ns":120,"title":"Item:Q1684937","lastrevid":57481515,"modified":"2026-03-31T02:58:00Z","type":"item","id":"Q1684937","labels":{"en":{"language":"en","value":"Proper orientations of planar bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6817811"}},"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":"Q1684937$342BC5EA-4B69-4FCE-B4F8-CB1EA95509C2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cddf149ace8114f9cdce2b12d4f8d56c4792f8a2","datavalue":{"value":{"text":"Proper orientations of planar bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1684937$61EE580F-8694-43E3-B572-B8ADD65086EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c46b1fa0d5848bc1c8b803d5f5e7c68ef792c1c","datavalue":{"value":"1380.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$3F48D94C-76DC-4EB9-AB6C-41393097C060","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0c0095365b969a11ebb363b04745c280e3f16db","datavalue":{"value":{"entity-type":"item","numeric-id":475263,"id":"Q475263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$88376B69-9231-4709-BE5B-AAC0D24CBF23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb25aa55fb3d1baf9ab36b30ae5b4252d5fb4710","datavalue":{"value":{"entity-type":"item","numeric-id":298991,"id":"Q298991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$4E44A317-B574-4FF5-A100-73A00F1A21F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9272e5e04b70c324ebdf831fbf42b90d5f6489a","datavalue":{"value":{"entity-type":"item","numeric-id":1684935,"id":"Q1684935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$05BE3514-9AC9-4B6F-8A5F-F20257DEAAED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$3DBC48D1-8EFD-4815-B93D-629DAB85EF77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74e45c3f99221d7833194d9c586d4b22f068b569","datavalue":{"value":{"entity-type":"item","numeric-id":189439,"id":"Q189439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$9325991F-8CBB-4926-BC03-96B91AD14807","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$BD1E85B4-85B6-4D41-88D9-036B758BE7CE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2c9e510587ef8cd6be004ed8dc7978b16550b95","datavalue":{"value":{"time":"+2017-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1684937$AF5B409D-2FA7-4BC7-AAAE-65095E344597","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d60855befdcbb49eeeb315959177f1570dc46ec","datavalue":{"value":"https://arxiv.org/abs/1609.06778","type":"string"},"datatype":"url"},"type":"statement","id":"Q1684937$DCC73027-35C3-4E6C-AB0C-F2D3E407B909","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"077797eb9bca5d487bb9f9b37cc0cca1fed680ce","datavalue":{"value":"An orientation of a graph is proper if any two adjacent vertices have different indegrees. The proper orientation number of a graph is the minimum of the maximum indegrees taken over all its proper orientations. It is an open question whether the class of planar bipartite graphs has a bounded orientation number.  The authors begin with a new and useful result that yields a polynomial-time algorithm to properly orient a connected bipartite graph, and to do so when controlling only the orientation of a spanning tree and the edges incident with one of its leaves. This algorithm produces a proper orientation with indegree at most 6 for a 3-connected planar bipartite graph, and with indegree at most 4 for a tree. (The later bound was known but the proof was not constructive.) By modifying their general construction, they show the proper orientation number of a 3-connected planar bipartite graph is at most 5.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1684937$4471FEEF-8BBF-4970-B677-7BBE57BD1437","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"33e4513cc2864d6aaaa2eed9f12761e45a15b7c2","datavalue":{"value":{"entity-type":"item","numeric-id":1684936,"id":"Q1684936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$BB461522-C571-4141-BBFE-3E2A401AAA8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$69041401-8FD9-400F-BD33-B4E0E57BBD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$8249C8D0-C30B-4763-AFD5-D53E692C0FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$38147E50-1DC7-4F85-85E2-7ECF767A25FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8229692c403358429a458476658f60fdd22fac4c","datavalue":{"value":"6817811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$23E2798F-CD52-435C-A15B-803A57365C77","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35975527aae2db20b3ef770a36f4aa53bb5e30a4","datavalue":{"value":"proper orientation number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1684937$6A7141CE-9AAB-4A10-8CE3-256F74E4399D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1684937$0920866E-1CAB-43BB-840D-7CC0D74D480C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1684937$1A0DE157-9E92-4B12-9299-B2BD350E57CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1684937$593B4D32-E3A5-424C-8203-08AF26498EAE","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":"Q1684937$F409B9EA-6ACE-4A20-981A-8578B75F90E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8724ce230a3112cd4d178758a13730700e6e0352","datavalue":{"value":"W2963514883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$F37CC075-3EDF-4180-9ED4-100EDAFE58D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00886c5bd7c9b5d1d32a8d0cc540dbfa6298e759","datavalue":{"value":{"entity-type":"item","numeric-id":2445254,"id":"Q2445254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$9AF7628A-0E2C-4122-969B-E4982E91E6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"316224a388fa5a6273c05f3cc9629b7a5cbce458","datavalue":{"value":{"entity-type":"item","numeric-id":484321,"id":"Q484321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$7196B763-DF4B-488C-A51E-ABF02DDF14E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"417f695b02aa947ed9327c29e3ce72d6b20958a4","datavalue":{"value":{"entity-type":"item","numeric-id":301589,"id":"Q301589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$132C364E-6FAD-4E71-8278-99B5B152247E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60ecde349db9e2565075e503c730b4ba3c7a29ca","datavalue":{"value":{"entity-type":"item","numeric-id":5516076,"id":"Q5516076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$3E0633D4-C02B-41A5-ADEE-79340DB59A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c439d80aa48b2235589f2742abd16fc8d19d0fd","datavalue":{"value":{"entity-type":"item","numeric-id":2532282,"id":"Q2532282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$EBAC8B2A-1F5F-4E20-84CA-D9755F6B94ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63cba2656c704dd7aeb86307a6d9f1bc86b41e28","datavalue":{"value":{"entity-type":"item","numeric-id":1011698,"id":"Q1011698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1684937$1FC5E56E-2BDC-4E44-9799-37AF8E440304","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"34cf4edfd21981c2ef1908bd7504321fa9daf6b5","datavalue":{"value":"10.1007/S00373-017-1836-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1684937$90259A2D-7FAB-4F85-A1B1-1EF7CDE58C2F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06667dcba788afcd9d35dce457eb24cac7a050bb","datavalue":{"value":{"entity-type":"item","numeric-id":484321,"id":"Q484321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1111b2c5bfebc5784c901ec96c92a520962bffe1","datavalue":{"value":{"amount":"+0.9243610501289368","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":"Q1684937$5F45B8C3-CF46-4A84-A88E-15C575561BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55d7faa291d5c4a610e9bc16568b0f12671a0cd3","datavalue":{"value":{"entity-type":"item","numeric-id":6038578,"id":"Q6038578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dffd447da02f109e576d0d0665faface487680a1","datavalue":{"value":{"amount":"+0.8616219758987427","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":"Q1684937$C191F9F5-E33F-44AD-A33E-45DBB070ACFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ab23f5c7590e78df44b57ed17405be5096d1626","datavalue":{"value":{"entity-type":"item","numeric-id":2043367,"id":"Q2043367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d86fcd7f91361e890bb3f1f1c6b0a0215b5c89d","datavalue":{"value":{"amount":"+0.8616065382957458","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":"Q1684937$B21C78B4-BE8B-4B61-B462-83DFAE91B581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9e74afa5735674b6bd3a5a118ccfcd4ba4529d","datavalue":{"value":{"entity-type":"item","numeric-id":2445254,"id":"Q2445254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba767f1dd03716715e40532b76e4c0ea49735d87","datavalue":{"value":{"amount":"+0.8385657072067261","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":"Q1684937$33761FD0-F95C-4420-98FA-043930744617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91a2daaf82aa54a1847210abe29f5040903a2cb7","datavalue":{"value":{"entity-type":"item","numeric-id":5066921,"id":"Q5066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9674ef50db673e9fa47deb74472c39b85ea1896f","datavalue":{"value":{"amount":"+0.8384765386581421","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":"Q1684937$DB873F5C-1C44-489B-AA34-5D6A14E87AAF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1684937","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1684937"}}}}}