{"entities":{"Q2482113":{"pageid":2492856,"ns":120,"title":"Item:Q2482113","lastrevid":50337980,"modified":"2026-01-13T20:39:40Z","type":"item","id":"Q2482113","labels":{"en":{"language":"en","value":"Planar graph bipartization in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5264547"}},"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":"Q2482113$31DEAED3-124D-444B-BA7C-F91F91199176","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"061443107cf0bb5564b8f1645ac1f18d4fe22188","datavalue":{"value":{"text":"Planar graph bipartization in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2482113$47EE75AB-156D-4897-A894-8DAE732F496F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a641ff24672dfb8579267c313e0c437cb3760edc","datavalue":{"value":"1163.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$64A872BC-DA50-4D97-980E-2276AB28D4F0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6be138e27f4fbac72f6efdc6dc3eb9c65525ae8a","datavalue":{"value":{"entity-type":"item","numeric-id":210516,"id":"Q210516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$ADE828DC-0EBB-4E5E-8DAB-AF7A90A44FDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef8936535173b0539c6142dcfc4232d85132bf03","datavalue":{"value":{"entity-type":"item","numeric-id":877198,"id":"Q877198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$0238F2A3-4721-4617-AEFD-BFEDE4D86C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b98dfd69e695d361ad845eeb3c42cf13105fa89d","datavalue":{"value":{"entity-type":"item","numeric-id":487015,"id":"Q487015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$0F0FEB72-2712-4A49-917B-05B70C86EAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$3C88ED61-65FF-4E64-989F-0CB7117B8F0F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$AA3D8D26-B485-42E1-8EEE-855A0A3A86BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6a5658e642f3500324f78b23f55b5ff809190c23","datavalue":{"value":{"time":"+2008-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2482113$DEA10DFB-8CE2-493D-B459-10ED75526575","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e0eca180334123d3cba517d04d2fce2be72ac403","datavalue":{"value":"This paper studies a parameterized version of the fundamental graph bipartization problem: given a graph \\(G\\), decide whether \\(G\\) can be made bipartite by deleting a set \\(S\\) of its vertices having cardinality at most \\(k\\), where \\(k\\) is a fixed natural number. This can be done if the graph has an odd cycle vertex transversal of size at most \\(k\\), i.e. a set of vertices \\(S\\) with \\(|S|\\leq k\\) that hits all the odd cycles in \\(G\\). In particular, the authors focus on the bipartization problem in planar graphs. In this case, one may look at the properties of any plane embedding of the given graph \\(G\\). Then, the key observation in the paper is that a set \\(W\\) of vertices is an odd cycle transversal of \\(G\\) precisely if every face of \\(G-W\\) contains an even number of odd faces of \\(G\\). Starting from this observation, it is shown that if the graph has the required property than it has bounded treewidth, too. Moreover, it is observed that the bipartization problem for a fixed \\(k\\) can be expressed as a monadic second order logic formula, which entails that this problem is feasible in linear time on bounded treewidth instances. Nevertheless, for completeness and in order to give a more efficient technique, an explicit algorithm that computes a minimum odd cycle transversal for graphs having bounded treewidth is also described in the paper.  In summary, we get a linear time algorithm to compute a bipartization of a planar graph, if a fixed bound \\(k\\) is given. That is, this paper shows that the bipartization problem is fixed-parameter tractable for planar graphs. I found this paper very interesting. However, possible readers interested in practical applications should consider that linearity here (as in the computation of tree-decompositions used in the proposed technique) hide very big constants that in many cases make such algorithms impractical.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2482113$F067BC91-BD02-470B-B218-224882A72690","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c163cf9e2c84e9609663c52d74f65382b10c74a","datavalue":{"value":{"entity-type":"item","numeric-id":235708,"id":"Q235708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$8008DBFA-ADFD-49D1-BC06-A647B6285F84","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$AFBCD091-1019-40DE-824F-AF575F6E941C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$0C3C94F8-96F7-4C7E-952A-1BDDBA2313CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$4D229036-DC34-4A3D-A6FF-ADB36AF4BEC2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5029d239f41e66f2cd72325e0b1108918a341167","datavalue":{"value":"5264547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$387D9FF1-3542-428A-859A-B2EE753D3EF1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2482113$EE539AB8-80FA-4EDC-938C-BB0E5CC82D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6632d6c62ffd85f90b0b4aa23149cd1a8c7ae150","datavalue":{"value":"odd cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2482113$4DB5F214-5B59-4988-969D-7FD1A9186131","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2482113$D450C330-4147-4510-8BB9-712136A54CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2482113$1F036CEF-E045-4809-8AB9-1CA2CD861E2E","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":"Q2482113$5A3B0F86-1322-46A7-8FEB-48970D7ACA13","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"427451d6079037009dd263498ce6463c0819da99","datavalue":{"value":"https://doi.org/10.1016/j.dam.2007.08.013","type":"string"},"datatype":"url"},"type":"statement","id":"Q2482113$0CE15D67-660B-4805-9285-815FA9F4401C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"356501329e4f3a01a9894326f8ba7a0152a64bd6","datavalue":{"value":"W1991223992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$E5B27C52-BB31-46CF-9A02-DCBB09A5A362","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc7a829d7c9eac0cb8489d464804900afba5db26","datavalue":{"value":{"entity-type":"item","numeric-id":4296512,"id":"Q4296512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$BD88ED89-025E-4B2C-ABE5-F445254C3C1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$82ACABDB-81C6-4B27-BF8E-38914BA2D56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$A54D7A98-51C3-48BC-8001-FE0309A86E34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed1f9dbcc46171640b27ee2fc39e713fa04c5a8","datavalue":{"value":{"entity-type":"item","numeric-id":1307344,"id":"Q1307344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$C85183D7-1040-4BD6-96FD-8F7E3D232E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$DC878773-2A20-44E5-AA4B-7C74BC6E6586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$3EB0878C-85B7-41F9-BBB3-9D32E382DD35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab04b7dd603409eeca0d677c90e92246cef0ee81","datavalue":{"value":{"entity-type":"item","numeric-id":4252334,"id":"Q4252334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$7F3735BC-2726-463F-A5BF-D95A4664E7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e885285ac923d2af4c5ca52739a73585b735e45f","datavalue":{"value":{"entity-type":"item","numeric-id":1425111,"id":"Q1425111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$0084D106-88BE-4DEB-8ABA-A719756AFCB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b04f097f7dc1fd904f6cdf5a8381ac06fb83404","datavalue":{"value":{"entity-type":"item","numeric-id":4173379,"id":"Q4173379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$562A9CF6-A89E-4D15-BE74-83358AD7EB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d46c3ff8da4cd71c5017da9c54ed62a304d85604","datavalue":{"value":{"entity-type":"item","numeric-id":1125684,"id":"Q1125684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$5616C9B2-2B94-4D16-9902-A7B28646AD61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d447ad530189f5ccd64ed649963313ae132d1a5a","datavalue":{"value":{"entity-type":"item","numeric-id":703225,"id":"Q703225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$99726033-BB5E-4B6A-873E-DBE8A1AA569B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56f7724e958b9375cd17e450965db24f772592ed","datavalue":{"value":{"entity-type":"item","numeric-id":4408101,"id":"Q4408101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$E752FB48-5942-486C-8142-12EB9922D840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$CF69A3E3-E226-44B3-914C-6C7A51C99961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a583b336166cebbddf1ca439ee3458ed6982ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1338321,"id":"Q1338321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2482113$5CD740F9-197D-4B1C-8116-685E38F8D8D2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b125baf074a80ea82835613ff60e8f41a4b8f55","datavalue":{"value":"10.1016/J.DAM.2007.08.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2482113$7EA8E283-E12B-4AA4-986A-A28C4AA82A9A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa42aa7236892340095d8f599cf6447531c1589f","datavalue":{"value":{"entity-type":"item","numeric-id":2301359,"id":"Q2301359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38336b72820402b8dbcfc44429a35dfd164fc5fc","datavalue":{"value":{"amount":"+0.8423975110054016","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":"Q2482113$AF5CFDF7-43D7-45F5-BB88-F522E8B1D7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75878f0dc394f4e6cdeb914b358d471d4407769e","datavalue":{"value":{"entity-type":"item","numeric-id":3043700,"id":"Q3043700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4134a042207b376d96aed6442516445a97a2d641","datavalue":{"value":{"amount":"+0.8044963479042053","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":"Q2482113$B3149B7B-E0A2-44F6-9E4B-481EDFF66905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01a8eb161265706e37700425bef90ef21b63afd6","datavalue":{"value":{"entity-type":"item","numeric-id":2498928,"id":"Q2498928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43f78cba99a0a8591a095e9ec9ff4fac6864cc50","datavalue":{"value":{"amount":"+0.7926382422447205","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":"Q2482113$B920FF73-41B4-4855-8F53-BE57924170A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acf09d88f3794a593e42e1ee6cba49aec70720fe","datavalue":{"value":{"entity-type":"item","numeric-id":3627967,"id":"Q3627967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d134eb23073b90cad4eeea0d297ed7114b37a6b9","datavalue":{"value":{"amount":"+0.7915399670600891","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":"Q2482113$D124892A-1E5F-45F2-98D9-DF47498C6E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c4acd401c156467d4bb8ec0c54706c28be71e92","datavalue":{"value":{"entity-type":"item","numeric-id":4634410,"id":"Q4634410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5e1171800541bf6791c3ee95987c01337053657","datavalue":{"value":{"amount":"+0.7870774269104004","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":"Q2482113$710BE7F0-C7C6-4D68-B7F2-A4EF82EF032A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2482113","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2482113"}}}}}