{"entities":{"Q5955209":{"pageid":8132011,"ns":120,"title":"Item:Q5955209","lastrevid":93514481,"modified":"2026-06-05T04:31:50Z","type":"item","id":"Q5955209","labels":{"en":{"language":"en","value":"Existence of polyhedral embeddings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1703967"}},"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":"Q5955209$C9DE86EC-D7D6-44F9-929B-F311B26B7156","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fb6de919ed409cea5e7f33396618e3d06ff71f2","datavalue":{"value":{"text":"Existence of polyhedral embeddings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5955209$513E7C6B-BB87-43DB-954C-5993A3E330C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"002e86754049d151d80705ce3b7f287a615e3436","datavalue":{"value":"0989.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$13180BA8-01F1-4AC8-9EF0-F66FDBFF7DA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5955209$03CA2DFE-DA6C-472E-965C-B5F125D7A109","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5955209$93E73EC7-2D05-4820-830B-82BEA8969D66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e53d5fe2003f37e7673c4ddbbdb683b0d090f84","datavalue":{"value":{"time":"+2002-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5955209$F870D9C5-2808-4B68-8F71-24AB75899025","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c58ad30f5eca73845b4b3ef4edfa2f296d785a5b","datavalue":{"value":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.387.6171","type":"string"},"datatype":"url"},"type":"statement","id":"Q5955209$8CCA3412-6BDC-40F4-8CA6-39C23011F40B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20ee7251717d13e36cbda57c1b7d874b6be80fdf","datavalue":{"value":"\\textit{C. Thomassen} [J. Comb. Theory, Ser. B 57, No. 2, 196--206 (1993; Zbl 0794.05025)] proved that the decision problem whether a given cubic bipartite graph contains two compatible Hamilton cycles is NP-complete. Here, the decision problem ``Does a given graph \\(G\\) have a polyhedral embedding'' is proven to be NP-complete by constructing, from a given 2-connected cubic bipartite graph \\(G_0\\) a 6-connected graph \\(G_1\\) which has a polyhedral embedding if and only if \\(G_0\\) has two compatible Hamilton cycles. Moreover, if \\(G_1\\) has a polyhedral embedding, it also has an orientable polyhedral embedding.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5955209$5608C084-33CA-47EA-9129-F1065BF34D29","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"489b50af879f20c258267402ff7bb6342fefbc88","datavalue":{"value":{"entity-type":"item","numeric-id":588147,"id":"Q588147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5955209$794919F2-1E26-4C9E-BACA-CB63551A5810","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$9B4FF054-C1F7-4CF1-9E24-CAE932155621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$DC3B1BDD-B662-40DB-A88D-747946D4BB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$766CB571-A5E8-4EE3-9667-998AA5878A8F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"047236039046b581e54b47ccb07b364e8782a56b","datavalue":{"value":"1703967","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$C385AB99-E106-4E06-AC21-B500C8FE66B8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2e239840c06c49fd3afbb70be0ec267643a9bc3","datavalue":{"value":"polyhedral embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q5955209$A2368A9F-8678-4990-BE3D-429DFF2210E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5955209$E15F1008-EB12-4694-AC3B-C801E9E49251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24ee27feab6365a1168b8c97c8d165cd061c4be0","datavalue":{"value":"face-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5955209$AEEB2633-03E3-4944-A129-368D1FE6B95E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q5955209$BB70A2E3-F8D9-4F20-8D65-FE01E4300777","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":"Q5955209$BF1B02AA-6628-4977-9E05-8B53932A8989","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"319a193ed0b86ad1f6ae53351c7ab57218338c6e","datavalue":{"value":"W2113363067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$A2A7338D-41F1-45DC-ABB7-9ADBDB521810","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf0840fb1387c012a4ddb10e1e78ffd99c32fe65","datavalue":{"value":"10.1007/S004930100003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5955209$D6253D8B-D4F2-454B-AFBD-A2159342387E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b1c6579fc747fedc5770ed2816f7d0653d05a0e","datavalue":{"value":{"entity-type":"item","numeric-id":1325240,"id":"Q1325240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f18c3a27639f786608d9d9ea7f2c604158e99bb8","datavalue":{"value":{"amount":"+0.8141284584999084","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":"Q5955209$BDC363E0-79A7-4E9F-92AE-0ADABAF498C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7a203e3d48628752ab581776b52cab67202d5b","datavalue":{"value":{"entity-type":"item","numeric-id":3325758,"id":"Q3325758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71285e06979352e8d166889a96ebb8ea0df86207","datavalue":{"value":{"amount":"+0.7841275334358215","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":"Q5955209$00B43A53-829A-4147-93E7-754D4411089D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47dd3d41aa4cf94928a59670f404111c9477c47b","datavalue":{"value":{"entity-type":"item","numeric-id":602768,"id":"Q602768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b347d32adcf2aac3cb81b38b44c323569a073d61","datavalue":{"value":{"amount":"+0.7796282172203064","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":"Q5955209$998D504C-4EF4-464E-91A0-C66205D4C6D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54e629448bbc0b2c1457ff5d810659085b0f9100","datavalue":{"value":{"entity-type":"item","numeric-id":4864467,"id":"Q4864467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c95bb95e48c92cc3a420eaddd2b1707ba7391e08","datavalue":{"value":{"amount":"+0.7752652168273926","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":"Q5955209$6B46416B-EDFE-4B2C-A8EE-5A5D127931FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"676fc79b30ebf628f1a51325849ba8bb22dbf831","datavalue":{"value":{"entity-type":"item","numeric-id":1354116,"id":"Q1354116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e00300baa690b184d059e764aec97b80f1dc744","datavalue":{"value":{"amount":"+0.7686205506324768","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":"Q5955209$E4EEB3B0-96EB-4FEC-A6CE-8262E82D3F59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Existence of polyhedral embeddings of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Existence_of_polyhedral_embeddings_of_graphs"}}}}}