{"entities":{"Q1971016":{"pageid":1981758,"ns":120,"title":"Item:Q1971016","lastrevid":46910094,"modified":"2025-12-25T20:21:04Z","type":"item","id":"Q1971016","labels":{"en":{"language":"en","value":"Note on geometric graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1421335"}},"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":"Q1971016$C0B4D8CB-9CDF-47A8-A5D3-B4B9C353BEAD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63db1f06510f40f72023c049a7921620cd6e3066","datavalue":{"value":{"text":"Note on geometric graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1971016$A8A0B0A8-58B0-4152-B158-B01225705AAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ccd6804f61f713fbf41703de156b6e966aff8ff","datavalue":{"value":"0951.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971016$3A21FD22-A64E-4CCF-BF25-D89B29CB1FD3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$1A39C1BF-3C09-40AC-932C-C2E3F8F10C0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5292801f0dd79298539819e0a4ac0e822803e06","datavalue":{"value":{"time":"+2000-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1971016$D225E367-BF0F-4CDE-9F6A-38CB1FE31DA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e78377bada074b8a3fda09af65a29ccd8dfe638","datavalue":{"value":"https://semanticscholar.org/paper/25b8963164725fc4d1dd3323a319fc5b4dd7a24e","type":"string"},"datatype":"url"},"type":"statement","id":"Q1971016$A853AC23-4352-40AC-A9DA-A86C410F1C5C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ceb0d4779c4135313bd2639aeec9eaf69431d49","datavalue":{"value":"The vertices of a geometric graph are points in the plane in a general position and the edges are (possibly crossing) line segments connecting the vertices. The article addresses the problem of determining the smallest number \\( e_k(n) \\) such that any geometric graph with \\( n \\) vertices and \\( m > e_k(n) \\) edges contains \\( k+1 \\) pairwise disjoint edges. The best previously known upper bound \\( e_k(n) \\leq k^3(n+1) \\), for all \\( k \\leq n/2 \\), is due to \\textit{G. T\u00f3th} and \\textit{P. Valtr} [Geometric graphs with few disjoint edges, Discrete Comput. Geom. 22, No. 4, 633-642 (1999; Zbl 0939.68097)].    In the article under review, the upper bound is improved to \\( e_k(n) \\leq 2^9k^2n \\), for all \\( k < n/2 \\), and this upper bound is shown to be sharp apart from the value of the constant for all \\( k \\) in \\( O(\\sqrt{n}) \\). The nice simple proof of the upper bound takes advantage of a clever organization of the edges of the geometric graphs with no more than \\( k \\) pairwise disjoint edges into a limited number of length-limited ``zig-zag'' paths.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971016$CE2280CB-AF97-4944-8AFD-A53710BCA87C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971016$8D6A1B8F-48EE-4C5E-B2B0-493D9686EA11","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85d41830d46d4e19cd1c66f2231acc962912b321","datavalue":{"value":"1421335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971016$B33AB701-8DEB-41E9-B7AC-9F98C05FF68C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5275d8eb5844b28a3114b24364f6516be1bba999","datavalue":{"value":"geometric graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971016$2E3DA9AD-98A7-4681-9D83-E85D84829356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d52dfe74bfae48d1d6fae4dced71b69b56acba4e","datavalue":{"value":"pairwise disjoint edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971016$983110C0-7593-43BC-BA3B-5E7E3472B12A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1dc5e40d7a8a3386725a84b223a56083987b2ef","datavalue":{"value":{"entity-type":"item","numeric-id":178539,"id":"Q178539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$1AEB2336-5BF1-4917-AF0A-1CC6783FF838","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"35eaf61e442e867df19139f413c267c580a3f0bb","datavalue":{"value":{"entity-type":"item","numeric-id":162920,"id":"Q162920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$AD946307-735C-4272-83B0-FE7A6F8FC9DA","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":"Q1971016$01147C0D-1BC7-465E-8BFA-BCCD5C07B01F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d2aa1e1140e6cec4e1435a153b1d3d3ff3f3c370","datavalue":{"value":"W2005247788","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971016$349908B5-0CF2-436D-ACC7-5A8177C13735","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade0acd26dc2e418e3262ae3f3f4756c03bdad80","datavalue":{"value":{"entity-type":"item","numeric-id":5893809,"id":"Q5893809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$0653EEB8-C2E4-4C66-B226-D878DC705058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$1334B52E-F671-4452-A789-795DAAF3A7FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c27307114bb5624596e4c4ee4c0ae4149067cb1c","datavalue":{"value":{"entity-type":"item","numeric-id":3048864,"id":"Q3048864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$C8F306CE-4BA1-4EA7-B185-C8C60C5A400E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd09f6109a2a26b7c54c3011537519d170fdb9ba","datavalue":{"value":{"entity-type":"item","numeric-id":4314565,"id":"Q4314565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$D9D4CF9C-1ECB-4F47-8299-602F1190347A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f008ff6ef8ff17ba2dc931dfc3da0de1a1cc1976","datavalue":{"value":{"entity-type":"item","numeric-id":4339095,"id":"Q4339095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$6CC5E72D-D563-4BCF-AFDA-6D144A9EFE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fc3ececa13d0a020f6daca5d5aafdc66a408338","datavalue":{"value":{"entity-type":"item","numeric-id":1330876,"id":"Q1330876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$B8B301D0-D2F2-4F0A-95B1-5A1DED65DEF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9dad0587897d8d2e6fd99476945884bb1cafa8d","datavalue":{"value":{"entity-type":"item","numeric-id":1809516,"id":"Q1809516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971016$0D611AE9-3C94-4283-AF6D-C79AE0DE6937","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab95900e3b87f4d5372f409e196ae7aa00df9192","datavalue":{"value":"10.1006/JCTA.1999.3001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971016$D02A7778-12D8-4790-9980-904B1F1C5E68","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d160c4637c0ad91cf5786cc8da0624d1ed3308c","datavalue":{"value":{"entity-type":"item","numeric-id":1809516,"id":"Q1809516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4754b49fd38959da31510409235ba1e410f409b","datavalue":{"value":{"amount":"+0.9090207815170288","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":"Q1971016$CE054FEC-F460-4A23-BD53-C18BF9B1E6BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"530d8a5d187abe48933a8681d7dfdac0bbac3e15","datavalue":{"value":{"entity-type":"item","numeric-id":5925578,"id":"Q5925578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a30fb3f7d0367cffa0590f86b81c4f6d6ab3c60","datavalue":{"value":{"amount":"+0.881536066532135","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":"Q1971016$CC80E5D8-3DB6-4B1A-8B87-A18D8CD62751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa8db13f397e2b853c197018203b5215b4f9480a","datavalue":{"value":{"entity-type":"item","numeric-id":1916059,"id":"Q1916059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e883a5d702c4645b6ca746d3e73d05dc69e0df19","datavalue":{"value":{"amount":"+0.8800384998321533","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":"Q1971016$A52D4E1D-87BF-4010-B89F-35964BDFA051","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1971016","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1971016"}}}}}