{"entities":{"Q1396654":{"pageid":1407394,"ns":120,"title":"Item:Q1396654","lastrevid":68616549,"modified":"2026-04-13T00:57:04Z","type":"item","id":"Q1396654","labels":{"en":{"language":"en","value":"Pathwidth of planar and line graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1947219"}},"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":"Q1396654$6C44CBD2-8A27-4EA6-874A-BAA91DCA9FAE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad8dc75e0698034604cc374fb9931ab40b46f0bd","datavalue":{"value":{"text":"Pathwidth of planar and line graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1396654$6598AD44-29C0-4475-A3C4-D7F7706FDB8B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ffa5179069e8a51d2a02a43cca45e07c6fb7cccd","datavalue":{"value":"1029.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$5EF1A00D-3695-4691-8478-935B56B6A13E","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":"Q1396654$135E55FE-6C55-4A30-937D-D6492C0D313C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"371c78a66bb04aa36f866eec753ca0ef83c2657b","datavalue":{"value":{"time":"+2003-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1396654$26A1023E-6CD5-4C68-9321-4A7E0D493334","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4f95f6e77cbcc0a95042d0e4082ee35d51e7b07","datavalue":{"value":"The paper studies the pathwidth \\(\\text{pw}(G)\\) of planar graphs and proves that for any 2-connected plane graph \\(G\\) with pathwidth \\(\\text{pw}(G^*)\\) of the geometric dual graph \\(G^*\\) of \\(G\\) is smaller than the pathwidth \\(\\text{pw}(L(G))\\) of the line graph \\(L(G)\\) of \\(G\\). The technique of proof is appropriate also for the corresponding result \\(\\text{tw}(G^*)\\leq \\text{tw}(L(G))\\) on treewidths. Further it is shown that \\(\\text{pw}(G)\\geq \\text{pw}(G^*)- 1\\) for every 2-connected planar graph \\(G\\) of maximum degree at most 3 and the author conjectures that this might hold without the restriction on the degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$B28A6173-EECA-4F0A-872D-45F5790B9990","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$0360E20B-5181-41CB-AB08-6563521A6F2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$6D9CAAE1-7BE0-4670-85A4-DF547C7AC276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$EB49E514-BAF7-4A0A-A45C-2493AA3CB684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$ADADB94B-47A6-4A4A-872C-E98597FA90B5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"370ddd0f5bb381537dcad225392f2e97226c1753","datavalue":{"value":"1947219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$5B9BDAF8-A311-4044-8087-C7AD6041BA4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67f458d393b772a7cf36a53976d2b5be911e683d","datavalue":{"value":"pathwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$A83076AB-F355-4417-B21A-CCB6518524F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$CD3905AE-510A-4F38-91EB-D021DEE2476C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$9D0ACD28-EF2F-449F-A338-24A7EFAD77E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e77b229532a8249bff86420a515b82c08ef4fb3","datavalue":{"value":"line graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$1C9294E5-6F6B-4A19-AF49-3BD7D75ECF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66e7957a80ee9b15bc3d1e2944fbb786e9926d58","datavalue":{"value":"cutwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$D3AFC5E5-07F8-4ED8-BFBF-AD40E3CF339C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99fb8c69c202cd08d29b22488e32432b5a73c333","datavalue":{"value":"search number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$81201545-BF7B-4304-A438-C3F46DED1BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0061d444635dc200bdb029d136d17f52aa90a9e","datavalue":{"value":"dual graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396654$5FF8A42C-8D81-4357-8559-3AD81276B47C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a8874875f41e100f7dd0c90f8e9a202da131938","datavalue":{"value":{"entity-type":"item","numeric-id":259035,"id":"Q259035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1396654$D8356FB6-013B-487A-811C-953B1D3B826B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"84719a152f3d80016cc596ed87fee134f8b91808","datavalue":{"value":{"entity-type":"item","numeric-id":703682,"id":"Q703682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1396654$27CCF565-C994-4087-B186-2415F3707DF5","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":"Q1396654$B24CF0B0-3E16-497A-8456-209526AFE772","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"354da1c8f8f4367d0d93620c8fd740fcd1812777","datavalue":{"value":"https://doi.org/10.1007/s00373-002-0490-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1396654$C1E27D18-08D9-4EDF-A777-19DDAD71C66A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"430fe29dc8c6bb9ac94f9bf3c3c43d46b7013dc7","datavalue":{"value":"W2089840103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$10A1A21B-9A3E-40EE-B94B-D122A1BDF01E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a115c694fe8b9bac061712181c583e6db5ab63dc","datavalue":{"value":"Q60488780","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$12AD0E53-3708-4991-97F8-6C5CA5D3705B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aca850a145cf0eb00a532004c1e9c84c40836f01","datavalue":{"value":"10.1007/S00373-002-0490-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396654$7E8C6867-CC66-4B27-8A89-B40DD9D5C8DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"503bd4c3f4bde676f01ee0c64b9812f22bd1be2f","datavalue":{"value":{"entity-type":"item","numeric-id":3583303,"id":"Q3583303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8070733929076efdbedb5198c8a20d2a9f8813a7","datavalue":{"value":{"amount":"+0.8863712549209595","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":"Q1396654$3463268D-C9E7-43D3-BCDE-E53F4C975363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a612f2ae66a472ec1ec1c69d05e5c09fdde75626","datavalue":{"value":{"entity-type":"item","numeric-id":3445500,"id":"Q3445500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7f8cd53c0c18f1fe2e502f8aafba235b96df36c","datavalue":{"value":{"amount":"+0.8535277843475342","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":"Q1396654$E1A1831C-481B-43D0-9FB7-FF6E4DF37D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7302234b8c7934161034ef483f2f63a068d288","datavalue":{"value":{"entity-type":"item","numeric-id":3445501,"id":"Q3445501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74db9976ef8dcd168a7a40696f9e7818c0543e70","datavalue":{"value":{"amount":"+0.8451111912727356","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":"Q1396654$C99D7E1A-E0AF-4BB7-B21F-0167671CDA14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fbf9c64e6ba4b95ce4d4beebab09a8c2fb05b6f","datavalue":{"value":{"entity-type":"item","numeric-id":2827827,"id":"Q2827827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f200595044857128d03c1584816867b94ebd03a","datavalue":{"value":{"amount":"+0.8057084679603577","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":"Q1396654$8D9DADBB-BEA6-4782-B7F9-8ED7EF75B0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e0b9962787a9bafe2b90e9d76f802cd2a5be58","datavalue":{"value":{"entity-type":"item","numeric-id":414640,"id":"Q414640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1921f62ece3d84f8ea3271157363fbcb3b697fa","datavalue":{"value":{"amount":"+0.7811083793640137","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":"Q1396654$454ADF30-3234-47CF-ADA9-EF6AB19831E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pathwidth of planar and line graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Pathwidth_of_planar_and_line_graphs"}}}}}