{"entities":{"Q521397":{"pageid":523164,"ns":120,"title":"Item:Q521397","lastrevid":57051165,"modified":"2026-03-26T10:42:21Z","type":"item","id":"Q521397","labels":{"en":{"language":"en","value":"On the queue-number of graphs with bounded tree-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6703757"}},"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":"Q521397$066A25D3-C866-423A-BEC2-282E0BF292DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a34e26215fdf88f7460a534fa38df94b5c4e0d6","datavalue":{"value":{"text":"On the queue-number of graphs with bounded tree-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q521397$93730E30-3B23-4F2E-857A-D4D3CE4BF3F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98352d3b30096eba07684e02228d99345e9dd957","datavalue":{"value":"1358.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521397$378313B8-DABA-4F10-B900-20E3AD570927","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2edb636548564610f885e26ad5e4aed54e810cf9","datavalue":{"value":{"entity-type":"item","numeric-id":521396,"id":"Q521396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$5BAB2884-06BB-459A-BABA-CB737A4CFC2A","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":"Q521397$A308A979-ACC8-409E-97A4-0194FB063449","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c018a10501084d0b87c78551bc55b3f7e17eb53","datavalue":{"value":{"time":"+2017-04-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q521397$826758A6-26BC-40D8-B6DD-7B2F7B0AC806","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28c87bc5bd885a7ec3d02907bdc908a43da0f6f9","datavalue":{"value":"https://arxiv.org/abs/1608.06091","type":"string"},"datatype":"url"},"type":"statement","id":"Q521397$3BD3A508-C36D-40CA-8595-3CDA123BFF64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"536bb604971a9ae37d5dec821bbf8c576e1790b9","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p65","type":"string"},"datatype":"url"},"type":"statement","id":"Q521397$888347DB-542B-4521-81D8-402CCFE4AA42","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c08b18eb7d7540a0c23049ce5ed4c363fa7d389d","datavalue":{"value":"Summary: A queue layout of a graph consists of a linear order on the vertices and an assignment of the edges to queues, such that no two edges in a single queue are nested.~The minimum number of queues needed in a queue layout of a graph is called its queue-number.   We show that for each \\(k\\geq 0\\), graphs with tree-width at most \\(k\\) have queue-number at most \\(2^k-1\\). This improves upon double exponential upper bounds due to \\textit{V. Dujmovi\u0107} et al. [SIAM J. Comput. 34, No. 3, 553--579 (2005; Zbl 1069.05055)] and \\textit{E. Di Giacomo} et al. [Comput. Geom. 32, No. 1, 26--58 (2005; Zbl 1101.68066)]. As a consequence we obtain that these graphs have track-number at most \\(2^{O(k^2)}\\).   We complement these results by a construction of \\(k\\)-trees that have queue-number at least \\(k+1\\). Already in the case \\(k=2\\) this is an improvement to existing results and solves a problem of \\textit{S. Rengarajan} and \\textit{C. E. Veni Madhavan} [``Stack and queue number of 2-trees'', Lect. Notes Comput. Sci. 959, 203--212 (1995; \\url{doi:10.1007/BFb0030834})], namely, that the maximal queue-number of 2-trees is equal to 3.","type":"string"},"datatype":"string"},"type":"statement","id":"Q521397$E24CB0A0-7ECC-4085-A3D8-2E6E78AB038A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521397$4204772A-3431-4EE8-B66F-1AB86FFA9B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521397$BCE6C0A7-4D36-458F-954C-7C27DF661C64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76750c2dacc4e0dffc7bbcf29d37ae26d9e84608","datavalue":{"value":"6703757","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521397$76633DBB-0BAE-4FFE-8156-183A628E5301","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b8fe8c958396f0b28a7a39fad19172e78cf4102","datavalue":{"value":"graph layouts","type":"string"},"datatype":"string"},"type":"statement","id":"Q521397$34AA5406-7145-4BB0-B568-F39CF7849723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1db903d7e918d4fa8bc15711828f4c9ffc2922a4","datavalue":{"value":"queue layouts","type":"string"},"datatype":"string"},"type":"statement","id":"Q521397$D304636D-8A80-4B86-BEB8-A91EEE4940AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q521397$DEF72399-946B-4DAA-BD91-D6EC200EF0DE","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":"Q521397$61C8B0CC-6DC6-436F-AA29-38DE49E96E17","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$24F4EA1D-27FC-42B6-A884-BE38715926B1","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":"Q521397$5BE6A63B-5F61-4981-9B9F-372F4E1C39D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae38009c8bf9bab1061f4a389c0c393c2364eb07","datavalue":{"value":{"entity-type":"item","numeric-id":4679078,"id":"Q4679078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$9FC7F778-7AA3-4D34-8E04-E303F4F8677B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28cefb108853ac5d76c97c93edfe3d8a03348c42","datavalue":{"value":{"entity-type":"item","numeric-id":675316,"id":"Q675316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$455791D9-C2A0-401D-B077-25A1C1E4D0B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1a2b7d618031a252c9b2db37e0fe7befef16b05","datavalue":{"value":{"entity-type":"item","numeric-id":5408766,"id":"Q5408766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$ACE8DDAD-898C-4A2A-B4D0-3988583F1F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fe83a941613e87eef27fffb1eb7137dfb96ca02","datavalue":{"value":{"entity-type":"item","numeric-id":2387202,"id":"Q2387202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$6E3A0935-EE3E-4727-AC0A-8A8976FA3081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"057e7c48188a57c7008301c7a0c58d2db9ac31aa","datavalue":{"value":{"entity-type":"item","numeric-id":473100,"id":"Q473100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$77A80587-762D-4E2B-B0FF-D4F7E899B3DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b64a39c639a71142f8e4eeb971739cad969046cd","datavalue":{"value":{"entity-type":"item","numeric-id":5317164,"id":"Q5317164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$F6C35BA8-BB36-48BF-9DA2-E83366430D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c8f519ca2c24d87effaeaffe2a823e1425495c1","datavalue":{"value":{"entity-type":"item","numeric-id":4667610,"id":"Q4667610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$FAC0F772-F7CF-4FA7-AEC4-6CAF574B52B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3670e64bfd678cc80082d6fd5bbb39b8efc18d","datavalue":{"value":{"entity-type":"item","numeric-id":5193181,"id":"Q5193181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$625BA586-929D-4453-82DF-A8BFEE1B6BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9fe45bc41a495895c93027605e3b1bfb518dabc","datavalue":{"value":{"entity-type":"item","numeric-id":5387656,"id":"Q5387656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$9FB43A3E-5196-4031-8A98-7A13C884A5A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"061c46f54d84762d943e1c7949213c4a168b95b9","datavalue":{"value":{"entity-type":"item","numeric-id":2503149,"id":"Q2503149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$D19674F2-F619-4ECC-B469-7F67D831D33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d675f62019ad4b450cbe016ccd3a4e323388dc2b","datavalue":{"value":{"entity-type":"item","numeric-id":2407382,"id":"Q2407382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$0C872E11-FA4D-435F-ADCB-E16F584B2077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7de20ea62c6c62c593eca7cd15ba2eee950868ad","datavalue":{"value":{"entity-type":"item","numeric-id":4679074,"id":"Q4679074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$3893A60B-9DEE-4F52-8128-F9948E15210C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0526aca192c857d79db3dbbad9f928fc055bcdd4","datavalue":{"value":{"entity-type":"item","numeric-id":5931789,"id":"Q5931789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$6DB6FF0E-EDC2-4661-9F18-5741365A7EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45eae50cc9cf0ec893491ee19c53ffcecaa542f2","datavalue":{"value":{"entity-type":"item","numeric-id":2902890,"id":"Q2902890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$223C3D75-6DCF-4086-81ED-6D45B7F587FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e4de46336d0d07bf6a6ce03ddc464bfd06c1c01","datavalue":{"value":{"entity-type":"item","numeric-id":1183985,"id":"Q1183985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$C915F021-7BA6-4081-B866-090A76BD150D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b464876aeb4e7ab3c806fb47dd04927339cfa00d","datavalue":{"value":{"entity-type":"item","numeric-id":4018851,"id":"Q4018851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$6F42EF29-9583-41DA-9699-B98EA13D31DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ff436a1943b4ea6694b9f55741c91c233d4cf66","datavalue":{"value":{"entity-type":"item","numeric-id":4015976,"id":"Q4015976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$43DDB7FD-B008-4E16-A47E-34CB01133DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f11d285db7cbc011053d9d985bf96b0c3958541","datavalue":{"value":{"entity-type":"item","numeric-id":661943,"id":"Q661943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$D31588B6-3242-4E15-AC6F-D35B020B0D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f88a9f58f19411b688f3e91a923fd2776f60b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4225308,"id":"Q4225308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$12EBB7B9-FA56-4A5D-B210-6B1783C3FB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e04e86ffa165bce42bd1669cf3904538adf9b742","datavalue":{"value":{"entity-type":"item","numeric-id":4407447,"id":"Q4407447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$FEBD4D76-29B6-406D-A38C-BC20A70CCE16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8466e8a6030720c56a95c18502dfb44c526f99","datavalue":{"value":{"entity-type":"item","numeric-id":3692864,"id":"Q3692864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$B28D08E8-1E3F-41E7-8DE4-1096C64AE3D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fecfed5b95ff498335f554ec51cc3eda86a51cc0","datavalue":{"value":{"entity-type":"item","numeric-id":4415269,"id":"Q4415269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$5A68A836-EB98-4879-8099-0EEC25562953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eabecfaccdcc08142c60196dfe5c0b017e523007","datavalue":{"value":{"entity-type":"item","numeric-id":5387727,"id":"Q5387727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$373B2B0D-B889-423A-A36A-7FD7E3BC8A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd05e4b67b3a31abf197ae994d88fff07d3dbdbb","datavalue":{"value":{"entity-type":"item","numeric-id":1120582,"id":"Q1120582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521397$E75732A1-E1E4-4FE9-BD1A-09F853345620","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5ca6f0da72bf7562da9e06d87ca3fef96ae3b33c","datavalue":{"value":"bafkreigi7gmppfuerju4sz35hszc4db5dgxennjoqazfhpfw2ah6yaavvm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521397$326CCFAF-DDF1-4237-9042-8E74576AF085","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"073e4b2af4987737e4d3b8a0dfeaa0d279f47969","datavalue":{"value":{"entity-type":"item","numeric-id":5317164,"id":"Q5317164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a42355742e6d8324f2f6778151546de6a336a59","datavalue":{"value":{"amount":"+0.8837477564811707","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":"Q521397$9DA445BF-D220-45D9-BBCB-6A65E17884CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca67f7d8ff80f5d4752ec6a273751d659840a560","datavalue":{"value":{"entity-type":"item","numeric-id":5902522,"id":"Q5902522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"855ae4ff9cf538287fe06d7d17da798e1d9eaa49","datavalue":{"value":{"amount":"+0.864240288734436","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":"Q521397$2CD70A14-B9D6-44D0-A872-EAC9115A794C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ec3607cd316985c50ab43d642249b7d1d8d4921","datavalue":{"value":{"entity-type":"item","numeric-id":5915942,"id":"Q5915942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca409bf95104e76917636a77c72b21f156259491","datavalue":{"value":{"amount":"+0.8618745803833008","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":"Q521397$72CA77F7-9CCF-4886-A33E-3AE37DA09771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"024261c2a5f1508ae00f1d7180e80cf17b1b0e84","datavalue":{"value":{"entity-type":"item","numeric-id":5918924,"id":"Q5918924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4eb71897f58c18aaad3963f5d61fe614a1dba37f","datavalue":{"value":{"amount":"+0.8510577082633972","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":"Q521397$28C3C565-4F61-4B16-A85B-6ED8BC55B351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9515e9f46d00baf086cbb06c0520cb734a79c40","datavalue":{"value":{"entity-type":"item","numeric-id":4015976,"id":"Q4015976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"617cc3bb22a27dc1e1bfb3f2642ddce4b23388ec","datavalue":{"value":{"amount":"+0.8468452095985413","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":"Q521397$CE670DC9-6AA3-4C4E-85E8-16DD2EFF0B96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:521397","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:521397"}}}}}