{"entities":{"Q876504":{"pageid":878352,"ns":120,"title":"Item:Q876504","lastrevid":42741419,"modified":"2025-07-09T18:14:41Z","type":"item","id":"Q876504","labels":{"en":{"language":"en","value":"Configurations with few crossings in topological graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5144506"}},"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":"Q876504$BD88AC75-405C-4A2A-9D57-0C8E12A8BF3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f2283337c290432b1098c59df1e8720ffa31998","datavalue":{"value":{"text":"Configurations with few crossings in topological graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q876504$BE1190A1-F4A7-4021-8DEE-EAE471F7E5D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3eb7effc13b5787abd0897740c20fb6f4f6891ad","datavalue":{"value":"1117.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$09CAE1B4-407A-4DC3-BA01-A940E7E88049","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c31e34753d6d88354136116eb637796e7d9ee9ae","datavalue":{"value":{"entity-type":"item","numeric-id":359744,"id":"Q359744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$93B81396-B8C3-4CAD-A5A9-ACD398A7F44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2af74afb35a3470ae8a4512b3119f296db00b7cd","datavalue":{"value":{"entity-type":"item","numeric-id":628157,"id":"Q628157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$4426CFFB-6684-471B-807F-2EE9F9BE6AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f735f8cae382ae08c1bfede73353a855afee3ea","datavalue":{"value":{"entity-type":"item","numeric-id":263275,"id":"Q263275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$AEBAB3C5-C641-41D5-AC1F-5AB5F35F2286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"83381eec9b184d4928dbc1724082cb2e43634626","datavalue":{"value":{"entity-type":"item","numeric-id":334943,"id":"Q334943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$A5475A91-F51F-4C0D-A8DF-B987393E31A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$9A3205DA-48F3-4C24-A2EE-E673D8B88E55","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6f339c49c589764265da0f7de34a17b3e7a78e06","datavalue":{"value":{"time":"+2007-04-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q876504$3A0D36A3-539B-4B4C-89C4-DAF39955A813","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87379f964b7f6193ba42af866c68428127ed7531","datavalue":{"value":"A topological graph is an undirected graph \\(G=(V, E)\\) embedded in the Euclidean plane such that any two edges intersect in at most a finite number of points. The paper investigates the existence of special configurations, namely spanning trees, \\(s\\)-\\(t \\) paths, cycles, matchings and \\(k\\)-factors for \\(k \\in \\{1, 2\\}\\), for which the number of crossings is minimal. The paper also provides a fixed-parameter algorithm that tests in \\(O^*(2^k)\\) time whether \\(G\\) has a crossing-free configuration in the above cases. The fixed-parameter constant \\(2^k\\) is improved to \\((\\sqrt 3)^k\\) for \\(s\\)-\\(t\\) paths and cycles, while minor improvements are provided in the other cases. Also, each \\(O^*(\\beta ^k)\\)-time decision algorithm can be turned into a \\(O^*((\\beta + 1)^k)\\)-time optimization algorithm that computes a configuration with the minimum number of crossings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q876504$543B016D-9DC8-4B79-9365-A168EC26C16B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d995304e90e7beac4506488ba2a95d45629bb02","datavalue":{"value":{"entity-type":"item","numeric-id":589833,"id":"Q589833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$B1DE9461-D99B-472A-BDCF-885F795CEB7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$D0B12C52-5485-4561-9789-BF6C501F306C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$2535EBF0-21C0-4434-BAF1-DF9945DC8569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$EA7B387C-9F2A-422B-AB4B-9A42D354565F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74d1dd56bffe36fdd6f2614302ea8f1fbef13255","datavalue":{"value":"5144506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$1A457F90-FC32-46BA-A3D7-DBA66D5E164E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4eec67bd912792ecabc2ca38a171cd2c3b47a238","datavalue":{"value":"crossing minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q876504$1E1132F9-2684-465F-B584-875275CB1955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q876504$36A036CC-0872-419C-95DC-B075752D8D60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdd31bd27a7952322bda50b6d3d83e798c57764d","datavalue":{"value":"fixed-parameter algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q876504$0CB299CE-5896-4009-A882-D665B9533369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"634f1ede63f339f33c19c642c95e837ed378c116","datavalue":{"value":"Monte-Carlo algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q876504$0AB1E8DC-0941-4815-A747-07B2FBE40CE8","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":"Q876504$41CDF7F1-229E-4A9A-9820-6D6253267F29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"565cb5753d40bce8c3d383d68ff7aa92eedc3f41","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2006.06.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q876504$790135F5-AEC5-4FF0-82B5-CBEAA360785B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0cafdc90bb1fb40afc47f70ac573750ad37a0274","datavalue":{"value":"W2161036821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$01FD16BC-43F9-4A3F-9ED8-36329570F7B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$E8DEA9EB-FA0E-4D94-B565-0393ED8967F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c9817e2a33b8da2ba978fe817aa1156d29a976","datavalue":{"value":{"entity-type":"item","numeric-id":5492943,"id":"Q5492943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$9FC64D14-9138-4BC0-A8E7-A68FB8A2FD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a54e9556d0e87d1f5355b5f05145579079f4d33a","datavalue":{"value":{"entity-type":"item","numeric-id":1317860,"id":"Q1317860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$A3D66427-9BF3-4B41-A7EC-156B050B6C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4051110c4477fc08f60b17c5e19f6404488bd4b","datavalue":{"value":{"entity-type":"item","numeric-id":3357538,"id":"Q3357538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$402B0D9C-4861-41AA-89F9-41790C46732C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0470a7b1c8f4317860cba14a6850edf7e62b04e9","datavalue":{"value":{"entity-type":"item","numeric-id":5897893,"id":"Q5897893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$A7B5243C-CAEE-459E-936B-A12082C82B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1af4720a030643fa9b96086f914ab6cbb39e96","datavalue":{"value":{"entity-type":"item","numeric-id":688265,"id":"Q688265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$E1EB6CFD-D536-4188-A71B-87984B6E7C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f4e7516daa6d4014d6dbd7077864aea96730aa","datavalue":{"value":{"entity-type":"item","numeric-id":5826303,"id":"Q5826303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876504$EDA71461-805D-47F7-8054-A86B0FAC8700","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1226ba9abef0e5fa62ff8cbe4cec6d20349ec3e2","datavalue":{"value":"10.1016/J.COMGEO.2006.06.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876504$4CAA7934-A51B-44D1-8EE5-E48312E8AEC6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de94e65c8bcad9836ffa165622d3d6420eb65077","datavalue":{"value":{"entity-type":"item","numeric-id":5897893,"id":"Q5897893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e2da6c53f5a750999d81de2cca7409b6fb04c6a","datavalue":{"value":{"amount":"+1.0000002","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$2BF4CF90-C76C-441D-A0F3-197D1E76232C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38eee579b4111af390b93dc69713bf7def409f7","datavalue":{"value":{"entity-type":"item","numeric-id":2175439,"id":"Q2175439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a04d5eceb36a79f547e5738b3605ca7fc99469d","datavalue":{"value":{"amount":"+0.909424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$E987915A-8064-486B-BBE8-10F9ED2158B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ba2e56a3e0f50f697231e99880cdb4d50edbc6b","datavalue":{"value":{"entity-type":"item","numeric-id":5897637,"id":"Q5897637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d39997f0855e5f72905add4f1f8d766cb90572f","datavalue":{"value":{"amount":"+0.88996804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$D4DCB157-E784-4A1B-A759-B895989A8236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7dd41d4dd78bb91fc8e214469d54e41921b178c","datavalue":{"value":{"entity-type":"item","numeric-id":1011770,"id":"Q1011770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d39997f0855e5f72905add4f1f8d766cb90572f","datavalue":{"value":{"amount":"+0.88996804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$B63699BC-1939-4186-8486-782D1CE292F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163bc0685f79c11d90ca53690b7cd0c5980cefce","datavalue":{"value":{"entity-type":"item","numeric-id":3357538,"id":"Q3357538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4284c88812407c67f38c9f3c0292e7f7adeab59b","datavalue":{"value":{"amount":"+0.8869575","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$030FC901-124F-45B0-A09F-5B028AFDD843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"667082210e77f27cb8e3cff2acb28686ca91fec5","datavalue":{"value":{"entity-type":"item","numeric-id":5043129,"id":"Q5043129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06dfff4bac475fd3f93b6b37ba2d74cebc35cab4","datavalue":{"value":{"amount":"+0.8844909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$EFD7B793-CD7C-472B-94C3-32AF8D60658C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83babc81c869af9af57e2bd6e980060e206b4be7","datavalue":{"value":{"entity-type":"item","numeric-id":5346557,"id":"Q5346557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"155a1db8a51de52ed4affa7836412fc237c5298c","datavalue":{"value":{"amount":"+0.8838458","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$7A05D7D8-29F9-475B-A0E6-CFD389D53A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4005f927111f1694387031154dab9ada5faa19a","datavalue":{"value":{"entity-type":"item","numeric-id":3418609,"id":"Q3418609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9a1afd892e237d47a2e178b0efa6ad84428f1e","datavalue":{"value":{"amount":"+0.87857485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$F950EA94-4A95-4767-A8AC-FEF569E2475A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"544f370d9bd7c9ff0db8e0cf5f4aaedf5e7b82f8","datavalue":{"value":{"entity-type":"item","numeric-id":3595462,"id":"Q3595462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9a1afd892e237d47a2e178b0efa6ad84428f1e","datavalue":{"value":{"amount":"+0.87857485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$E026B2D7-DD49-40A0-8D95-47BC15D56A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97687b2f714ea5fc8c59460480ef12678526ebeb","datavalue":{"value":{"entity-type":"item","numeric-id":4552009,"id":"Q4552009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6131e2c2a3fbabb8c4ec6ed7c2e5116e6f40b2e","datavalue":{"value":{"amount":"+0.8774796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876504$49826304-9913-42D7-89C0-FC151E5DD9AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:876504","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:876504"}}}}}