{"entities":{"Q1841931":{"pageid":1852673,"ns":120,"title":"Item:Q1841931","lastrevid":70970427,"modified":"2026-04-13T18:36:02Z","type":"item","id":"Q1841931","labels":{"en":{"language":"en","value":"Monotone paths in edge-ordered sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1565960"}},"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":"Q1841931$F13D7AEA-646D-4C72-952A-A9300A59906E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb1763dce41001207ffe95ffba1779d4087e19a9","datavalue":{"value":{"text":"Monotone paths in edge-ordered sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1841931$DDB1C486-BF86-41B2-B4E0-46065ED9CEC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8943798e0a76ceca863da26f6059459bf21ec053","datavalue":{"value":"0961.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841931$912E2A04-EFBF-4055-B2D7-0C93BAF43FF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f1c8588b2919271f2b2c244caad1235d8795faf8","datavalue":{"value":"10.1016/S0012-365X(00)00174-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841931$ADF55E0B-06C7-4002-B5C5-8ED5D8E32C10","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"218f7dc4b63685dca32c01e904fc698ab2233c31","datavalue":{"value":{"entity-type":"item","numeric-id":590620,"id":"Q590620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841931$4008FDDB-7C77-4198-88A3-C2A055BA8D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cb1f535849edd0686cb766cad0896b213017ca7","datavalue":{"value":{"entity-type":"item","numeric-id":1841930,"id":"Q1841930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841931$06CAB842-00FC-4A6E-8070-85D93F611EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58695e9da83c43913be67e6d6be310d1075b58c8","datavalue":{"value":{"entity-type":"item","numeric-id":222643,"id":"Q222643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841931$2DC281F7-E94E-4B22-9B80-B5FB281302C3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841931$6327F625-6DDE-47FE-9742-9F9BBF27D87F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"766825f731087109bd78eadfd07796610a8684a0","datavalue":{"value":{"time":"+2001-05-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1841931$01FF9005-7B57-4895-B596-B1C65EDCB325","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e6ceb17ef4d0d21ab829413255cbefab163d897","datavalue":{"value":"An edge-ordered graph is an ordered pair \\((G,f)\\), where \\(G=G(V,E)\\) is a graph and \\(f\\) is a bijective function \\(f:E(G)\\to \\{1,2,\\dots,|E(G)|\\}\\). \\(f\\) is called an edge ordering of \\(G\\). A monotone path of length \\(k\\) in \\((G,f)\\) is a simple path \\(P_{k+1}:v_1,v_2,\\dots,v_{k+1}\\) in \\(G\\) such that either \\(f((v_i,v_{i+1}))<f((v_{i+1},v_{i+2}))\\) or \\(f((v_i,v_{i+1}))>f((v_{i+1},v_{i+2}))\\) for \\(i=1,2,\\dots,k-1\\). Given an undirected graph \\(G\\), denote by \\(\\alpha(G)\\) the minimum over all edge orderings of the maximum length of a monotone path. The authors give bounds on \\(\\alpha(G)\\) for various families of sparse graphs, including trees, planar graphs and graphs with bounded arboricity. For example, every planar graph \\(G\\) has \\(\\alpha(G)\\leq 9\\), and every bipartite planar graph \\(G\\) has \\(\\alpha(G)\\leq 6\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841931$B230D09F-267A-464E-8BEC-6DAD9AE041F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841931$D6EA881C-DF36-4359-A8A1-0BD4B8DDCA05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aaa8ed88159a485ec65d8e87095cea76f7fe6640","datavalue":{"value":"1565960","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841931$101E8A9B-CCA3-4B0C-B899-EF66F89163FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3fc3f306278971b47588c54be6220243123d7e","datavalue":{"value":"sparse graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841931$7B916ABC-B1A3-4F8F-9F95-627ED7B2B688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70277998ea2f6d2dc60df48f7d4ed3065749543b","datavalue":{"value":"monotone path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841931$5A27E0B4-0707-4462-8B4D-8FC3AAC9F3FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff806128c455b31542d0de9a5073495d9720236d","datavalue":{"value":"linear arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841931$8C9E59C7-21D1-4878-BB8D-4DEA70D75680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ee5b7f91928ea7204989a8eaf9baab734c8484f","datavalue":{"value":"star arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841931$FF10EB7F-4FE7-4078-BC96-1A6EEB9A9BC0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02baa8c7a177bdddffdd29a44a9d552f63adf459","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841931$EA019607-714E-4098-9325-88CB29F057D7","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":"Q1841931$496CB159-DEA9-458D-B2E1-A9B57A145EB8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd9645c832df9e7b862e811f98a85bcdd1c03b69","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00174-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1841931$9A208A1B-9CCC-496F-A339-A22F4E5B553C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6821a4c436456905001b97dbc18d1f2fd2ce57cb","datavalue":{"value":"W1976694075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841931$731711C4-3C0C-4ED0-BDD8-2190D420D545","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f56248ee575497bb58e20e13435a78cbb522eb37","datavalue":{"value":{"entity-type":"item","numeric-id":1095926,"id":"Q1095926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"653db33f57921bf4165267bbd42ce46462ce5c71","datavalue":{"value":{"amount":"+0.8802355527877808","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":"Q1841931$499467C8-2E4F-49FB-B03A-115983513DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcdac5733fdfa97676c10b1a585881fae86d4b01","datavalue":{"value":{"entity-type":"item","numeric-id":2200054,"id":"Q2200054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e68ca32ad946c97fd9aeeba879f58d1d8ba2b0e1","datavalue":{"value":{"amount":"+0.8506069779396057","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":"Q1841931$57490BE6-E8F8-4613-ABB6-82CEC383360F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20bd622247a6eb4c353568c7c8f1486bda3412ef","datavalue":{"value":{"entity-type":"item","numeric-id":2236638,"id":"Q2236638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9368506b15e60c36d71801bd26f76a55aa5ac3f4","datavalue":{"value":{"amount":"+0.8326244950294495","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":"Q1841931$E5E1CA6F-C04A-479A-9349-9E3A145116F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5193b2f82ef5f39cd275975e206c24c9ee9176c","datavalue":{"value":{"entity-type":"item","numeric-id":2404821,"id":"Q2404821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f397f23f05d5c15024c1e7a63a7ad65ee3e75e5","datavalue":{"value":{"amount":"+0.8302072882652283","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":"Q1841931$D9539B6B-D6B3-46CB-A272-28398DAF8137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b5ac3695e2af73d29ef3556da38d42f721b7f12","datavalue":{"value":{"entity-type":"item","numeric-id":602679,"id":"Q602679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3592e9d341abba5881c1bee2e5daf76b307b5529","datavalue":{"value":{"amount":"+0.8148282766342163","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":"Q1841931$53E8CEC3-29AE-4230-9BF1-04B94A42F51A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Monotone paths in edge-ordered sparse graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Monotone_paths_in_edge-ordered_sparse_graphs"}}}}}