{"entities":{"Q6827729":{"pageid":15106327,"ns":120,"title":"Item:Q6827729","lastrevid":56003215,"modified":"2026-02-24T12:30:02Z","type":"item","id":"Q6827729","labels":{"en":{"language":"en","value":"Simultaneous embedding: edge orderings, relative positions, cutvertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6872025"}},"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":"Q6827729$69687C0D-CC8B-4099-8578-FDB502AE6164","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a85ee94bab226df20dfebbdbeea152918fdf938","datavalue":{"value":{"text":"Simultaneous embedding: edge orderings, relative positions, cutvertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6827729$69EBE3D2-0EBE-4FCD-99CC-3BF84E48B888","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8f51a50d40b07e2eb8bb09b0156d25906c21cbd","datavalue":{"value":"1394.68263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$A173E532-95A7-49B3-A10D-6C9A70A3C424","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fcef613b27d48429d7c81135cbe2238311669b21","datavalue":{"value":"10.1007/S00453-017-0301-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$D395172F-6426-4E4E-B3F3-C6BB5C5EFBB0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1f2b9521209d28107f8b226b5b1287911a6230a","datavalue":{"value":{"entity-type":"item","numeric-id":476440,"id":"Q476440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6827729$5468A69B-1E97-4CB6-8C72-4170A80DDBA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4db6303ed29115a7c25c13fa8be92a47f373c933","datavalue":{"value":{"entity-type":"item","numeric-id":1751091,"id":"Q1751091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6827729$35537A26-2C11-4C1D-8CC6-44DCBB52BB29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49bbe852f04b340afb483710d250633e3c669542","datavalue":{"value":{"entity-type":"item","numeric-id":306262,"id":"Q306262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6827729$8927A786-5290-4CDA-89EA-CF71FEF47C2E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6827729$5C123C22-5C54-4F51-B958-1E2D6063A9A7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dbacccb69feaa544f1db3f76f439a42bd7b8d12f","datavalue":{"value":{"time":"+2018-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6827729$5D7BFAFF-EC0F-43C4-A00B-FB649BAD826E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e2b5dbb0a29bc0f91675444474aeb382c107574","datavalue":{"value":"Given two planar graphs, a \\textit{simultaneous embedding with fixed edges} consists of planar embeddings of each in which the vertices and edges that appear in both graphs coincide in the embeddings. No polynomial-time algorithm is currently known for determining whether two graphs admit such a simultaneous embedding, but the problem is not known to be NP-complete. This paper makes two main contributions. First, it develops linear-time pre-processing strategies for simplifying or reducing the graphs in such a way that a simultaneous embedding of the original graphs can be determined from one for the reduced graphs. Second, when a certain structural restriction on the graphs holds, an algorithm for simultaneous embedding that runs in cubic time is developed. The paper is quite technical, but is relatively self-contained. Obstacles to obtaining a general polynomial-time algorithm, and possible methods to overcome them, are discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$83FE1FB9-E7EA-4B63-9C89-0FE9A84FB75F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8ba0869bc4942831c8669ed75022f72a56f93072","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6827729$350D016B-521F-40A3-B9BA-3B8B1F5707A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$C9501D6D-CB92-448A-ACCF-0471736DE439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$EE1CD330-13C8-475D-8D81-E2D1CC272EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$36D8C862-36DC-472A-92C8-AB0C4A3F2FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$FABB7748-40CE-42E2-B711-5172B582B3B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a30350635690b53f0f0ab6dc7a9e1ad68b9b79f3","datavalue":{"value":"6872025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6827729$33E97B15-6A9A-4F0A-B10F-AF92C640C295","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$28E7AA9A-08E9-4075-B360-98AF3D4003DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ac20f6b43b82ae111d7d493632b1bd4a2ca4c0","datavalue":{"value":"planar embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$BDA1CF1F-93EE-43B8-AACE-6F11E4910773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4462bd4c4c1b6e2154d51b86477deec0a560a46","datavalue":{"value":"simultaneous embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$91A59D23-3F42-4B86-A472-37406C02771B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4364d21acd66d915b62f94bfe69e0065826249a1","datavalue":{"value":"efficient algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$CB46FA03-EE8C-4531-AA55-80983C827304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q6827729$5521B869-079D-4DF4-8483-EBC2AC5B3D1C","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":"Q6827729$00022790-1C16-46AD-AA39-4FF2CB582234","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Simultaneous embedding: edge orderings, relative positions, cutvertices (scientific article; zbMATH DE number 6872025)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Simultaneous_embedding:_edge_orderings,_relative_positions,_cutvertices_(scientific_article;_zbMATH_DE_number_6872025)"}}}}}