{"entities":{"Q1304472":{"pageid":1315222,"ns":120,"title":"Item:Q1304472","lastrevid":67511073,"modified":"2026-04-12T18:29:36Z","type":"item","id":"Q1304472","labels":{"en":{"language":"en","value":"Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1339914"}},"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":"Q1304472$3D8EB6F3-1BFF-4231-964A-BFF84E1088AE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"957b0c270120f732f2981a09ccac8a875631ef52","datavalue":{"value":{"text":"Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1304472$3B8B3C89-46AA-46AC-A28D-7111B116006E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6d852009ac9c36dcae77d8b68ca6cf6dafec2f5","datavalue":{"value":"0933.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$D77BBAAE-CBE3-4B57-B536-93026A222491","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"262038820fe9f76b345667cbe57b7e0c5aa8d925","datavalue":{"value":"10.1016/S0166-218X(99)00044-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$1A74DF6E-F317-4B0E-88FB-9C5E1172DAEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfa215cf6b30ee4d0ec9785cb7e068b69f1b3a72","datavalue":{"value":{"entity-type":"item","numeric-id":186104,"id":"Q186104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$1A9D2979-703B-49A4-BA4B-92D971254ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5504057f8e665d03ecf41f8625761123bee78746","datavalue":{"value":{"entity-type":"item","numeric-id":1304471,"id":"Q1304471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$E848EAB4-E106-4427-BC46-9338DEB8C7AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a57de2e11ea0a7c1b4e027ef0d1354f56003f3b7","datavalue":{"value":{"entity-type":"item","numeric-id":214980,"id":"Q214980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$9B797B1F-1955-40E0-82FD-5EBDD0BE5CD2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$4112F9A0-ECE8-4B9A-80CE-6A67B38D76BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d7fcc00a8ca0e7d2bba3b2e6904026043bd3d23","datavalue":{"value":{"time":"+2000-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1304472$D19C20E7-556C-497F-8BBB-DA3B18DF8DDA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"846168ec6bb3c0e788a7dbf7b7a51ffabb98754d","datavalue":{"value":"A topological book imbedding of a graph places the vertices along the spine and the edges in the pages; edges are allowed to cross the spine. Enomoto and Miyauchi (preprint) showed that every graph of order \\(n\\) and size \\(m\\) can be imbedded into a 3-page book with at most \\(O(m\\log n)\\) edge-crossings over the spine. The present paper gives lower bounds on the number of edge-crossings over the spine which show that the bound \\(O(m\\log n)\\) is essentially best possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1304472$9F108D6D-CBC5-498D-9940-C60AEC9E064F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$65972A9F-2CCF-4AA9-943E-D9DBD9BDFC1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$8B2D5BE9-A4E1-46ED-BF77-78701D901EA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d99d7551734156d9bdf0740900afee561726bbe3","datavalue":{"value":"1339914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$42FEF14A-96D7-47C9-9456-A4ECFECA0AD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fee4a9f251cac3eb3a2208e953f71921e4b2bf71","datavalue":{"value":"topological book imbedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1304472$895C6760-FD07-4F04-83F8-C8FE4D50BF59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8748a5930bbad83fa58069bd6595c1a615c933c","datavalue":{"value":"pages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1304472$39C620DE-0704-43D5-8820-4AD40DE951F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe84167af852e126b4b5340c81d9a9b19628c2b4","datavalue":{"value":"spine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1304472$CBA385A5-F957-4DE2-B3C8-4DC154127358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6a18baad1f43abada2147ff4124dcc3365864f7","datavalue":{"value":"edge-crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1304472$63B6CE30-4CAF-4E25-9900-4C3A133DB866","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"610da1c2476d161574cadf5cb4cee2db9d7152c3","datavalue":{"value":"Q56689187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$6A3882F6-53CA-4699-85E1-F864F3663F2E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$2398864F-9E4C-4578-A258-30B3B80D923E","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":"Q1304472$A70BB06F-C0AE-4FE0-B2E4-CA57FE803B05","rank":"normal"}],"P223":[{"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":"Q1304472$CD744D46-A9FB-4F25-904B-EC83C9145AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b602d01a898344ce4e168ea2188a5d94cd04e17","datavalue":{"value":{"entity-type":"item","numeric-id":4727445,"id":"Q4727445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$1F688870-7DF0-477D-947B-C37D0F16E9E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb59f7a7b9aad1b8c4f3ea7a20905a3f473cf5ec","datavalue":{"value":{"entity-type":"item","numeric-id":4699162,"id":"Q4699162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$8655B787-E804-480B-9474-C1F8FDAD3B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbe736b80d2bb6e8c9bdba6b3e218ee9bb21f494","datavalue":{"value":{"entity-type":"item","numeric-id":1386481,"id":"Q1386481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$7DAE1178-E4C7-4DEE-9977-E2AD492BA215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61877b197a38d8ad03aa3a4bc4c551805a18c531","datavalue":{"value":{"entity-type":"item","numeric-id":3812259,"id":"Q3812259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1304472$6DDE41EB-69FB-4B94-B0EB-14C6539BF007","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":"Q1304472$0F99F522-7827-4232-AEE7-B3A753B02289","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ffcfac7086a71cca5571749807ead1b9fdee3e13","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00044-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1304472$C04D57D3-EC0C-4041-8301-FCD3950C1A27","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec5d530ff425a9b2f3a65c62c1379d029e8c5d07","datavalue":{"value":"W2009528969","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$230C85A4-D32A-499A-BB2B-837CE6C27346","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"b03c209e25f1325a0ee02c0b5329bacfe5eda346","datavalue":{"value":"journals/dam/EnomotoMO99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1304472$CF38077B-3680-45C8-9601-10A28B206982","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d65166c4aa67644fe4133a4f426eec2c344bb92","datavalue":{"value":{"entity-type":"item","numeric-id":4699162,"id":"Q4699162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fee8067ebd5cba8ed332f1154f65b0ac48d1f25","datavalue":{"value":{"amount":"+0.9575545191764832","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":"Q1304472$B82B00BC-632A-424D-B194-13852AC4A28C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b13509bdeb68e74bbab37e23b9657fbe8ea772e","datavalue":{"value":{"entity-type":"item","numeric-id":4879178,"id":"Q4879178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a9899f6216e18ee268ec23f4ee3cf66e9e2871f","datavalue":{"value":{"amount":"+0.8109921813011169","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":"Q1304472$BAEC10FB-0242-4E15-AD2C-81622B8FCED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"024de375d6a319c530f9061bd5f52b216f065413","datavalue":{"value":{"entity-type":"item","numeric-id":4304061,"id":"Q4304061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cd1e8f159bd0ac55e5beea92b642a786bf0657b","datavalue":{"value":{"amount":"+0.7930524945259094","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":"Q1304472$7B3EB0D5-517E-4D82-BD5D-81F2AC2AEEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3b02d88dd351dfc9f4e6626a607fd1cdfc56352","datavalue":{"value":{"entity-type":"item","numeric-id":1379820,"id":"Q1379820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e13b30c7599e296957dd6e7cf7a7beedee29fe9","datavalue":{"value":{"amount":"+0.7701587080955505","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":"Q1304472$9F4937A3-FB8E-420F-AABA-3EF7A0711263","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_the_number_of_edge-crossings_over_the_spine_in_a_topological_book_embedding_of_a_graph"}}}}}