{"entities":{"Q1566702":{"pageid":1577442,"ns":120,"title":"Item:Q1566702","lastrevid":70727049,"modified":"2026-04-13T16:21:49Z","type":"item","id":"Q1566702","labels":{"en":{"language":"en","value":"The monadic second-order logic of graphs. XII: Planar graphs and planar maps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454552"}},"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":"Q1566702$8D6B37A8-B82E-42E9-8302-A70B65E2BBDB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49db03594323564b57cebfe9e61517a25739c0c6","datavalue":{"value":{"text":"The monadic second-order logic of graphs. XII: Planar graphs and planar maps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1566702$CDA6192A-4BC9-4EC3-BACC-F789D9FB3655","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98b0a4b555ab6bfcbf10846d86b80870a3081238","datavalue":{"value":"0951.03004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$083B1C27-FC1E-4D31-9446-6DBC90D2E8A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1406291b5d17039efbdeeea5151056a6a4e4c60b","datavalue":{"value":"10.1016/S0304-3975(99)00305-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$50126346-4EB1-4C11-BFD4-B8503572E8E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$2FAB47C7-AFF7-4DEE-B648-76E1A254E129","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1566702$DAED2537-FC90-455E-900F-858B2DDC3342","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7e0c6dcbddb383a76c920f27050915388b7c95a","datavalue":{"value":"[For the previous paper in this series see Zbl 0938.03015.]    As shown in several previous papers by the author, many important graph properties and constructions can be expressed in monadic second-order (MSO) logic. Here the MSO definability of planar embeddings of certain kinds of graphs is considered. A planar embedding of a graph is a relational structure that describes a circular ordering of the neighbourhood of each vertex. A graph is 3-connected if it has at least four vertices, is 2-connected and has no separating pair. It is shown that the planar embedding (unique by a theorem due to Whitney) of a 3-connected planar graph is MSO definable. Also for planar graphs which are not 3-connected, a planar embedding can be specified assuming that a linear order of the edges is given, but it is also shown that the ordering is really needed. Many of the constructions can be expressed by a new extension of first-order logic which includes special atomic formulae for representing the transitive closures of binary relations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$4BA4E1A4-D9C9-4750-A992-932C285A115F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$2F6606B8-6556-485B-AC02-3300BB2779F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$71B54BD2-E3D7-4EAE-9E6A-B72A7E945C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$8746EC1E-B702-46FE-BDC6-AB56DE71000C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d51af01cb81dfeb98811b111bd6414a673fa9753","datavalue":{"value":"1454552","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566702$4F8EE8E6-53D7-44A1-8973-FB7D99554DFD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5e0748da353cbaca68136c5462da6bce39666c","datavalue":{"value":"3-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$54A46BE9-908D-47C0-8340-62D95ACDF75D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$7DCCFE27-2450-499E-8826-973BAE555D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b40effcf301ae197364664191caf2e4984a3c49c","datavalue":{"value":"rotation system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$03C426A7-CC1C-4195-8455-54EDC8F92F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$251C1A5D-7FAE-428E-A92C-2D001459FE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$28EA2A42-D8D4-44D8-ABD4-F23132BEB430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4863d8223ca0268d13cc059998729a107a773223","datavalue":{"value":"ordered structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$A7723DE0-C577-4175-954D-EF4B53181EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aa00a4c4635da3e1a8927a353052773fcbd5326","datavalue":{"value":"depth-first search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$011DBB7C-2C89-4652-A43F-BB74D44EFF7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e3aefda6146ec01b513a4bbf21440f7e9242198","datavalue":{"value":"extension of first-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566702$2A93A058-2CA9-452F-80E9-BE79A493ED82","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$0527AFC8-D574-4574-8A09-43E7B86A11E4","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":"Q1566702$D5598A82-85EB-403E-A86C-64ED8C415F5A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$054654D5-79CE-4DF0-ADBB-B6FC7166C625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b439d6b5ea1e767aee9f4d150fbcd4d20c87b7f4","datavalue":{"value":{"entity-type":"item","numeric-id":1336623,"id":"Q1336623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$63B25600-7C5B-4281-8216-BEF7373A8434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e65180487d55de678beff9f15b2f64281465aaf","datavalue":{"value":{"entity-type":"item","numeric-id":1325847,"id":"Q1325847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$E26C5D17-F103-4741-B6CE-B54D4F35F999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8ded06ea25487612e26a0a728cfa41b8d8f646","datavalue":{"value":{"entity-type":"item","numeric-id":1842126,"id":"Q1842126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$06B2173B-8A25-4D21-A084-B3529AAA8611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aba5833662215ee6a49861d05418334754b27cf","datavalue":{"value":{"entity-type":"item","numeric-id":1366538,"id":"Q1366538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$61915905-4A0F-4DA7-AAE5-DAD86B2BC4C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a61f94f34b177df76a317c8d62663291a02395c","datavalue":{"value":{"entity-type":"item","numeric-id":4353558,"id":"Q4353558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$831D9DB5-FC18-40AD-BBC4-C2E22578495A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdc3bc37636162ea70f3f00e262d75f038d4aa3","datavalue":{"value":{"entity-type":"item","numeric-id":1960417,"id":"Q1960417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$F89EFEC9-9447-4732-819D-0D1118B55DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a34ff26b5dd0384a26c503ca4e37dfdbeeaea3d","datavalue":{"value":{"entity-type":"item","numeric-id":1575704,"id":"Q1575704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$16D2D312-4C05-4E46-93C7-3C2C164395C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f7063d0442c53e72e4d7aa07ea9c08e9fcc430f","datavalue":{"value":{"entity-type":"item","numeric-id":685464,"id":"Q685464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$598E7360-7415-43B3-A277-BD9FA6EE4881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751c6211e64b51a8e1aca9a77a723434c8cf281c","datavalue":{"value":{"entity-type":"item","numeric-id":4232773,"id":"Q4232773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$D3B31CAD-A5C6-413B-BE21-733565A27835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f80f6e19275125de4f8e2f83f2df184481d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":4342632,"id":"Q4342632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$1799A29D-3453-463C-9DC9-6C9C55467D8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c32b298b09103f7cc9eabedf752dc67f406d3","datavalue":{"value":{"entity-type":"item","numeric-id":4850061,"id":"Q4850061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$087FF297-FEBC-41BB-8EFA-D249F246E6D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d54116e22a2f6f77873234816c1a31a4470a693","datavalue":{"value":{"entity-type":"item","numeric-id":4936131,"id":"Q4936131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$64B9C41A-ED35-42DA-AE0C-6A5F4B6360EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade29bb9c5c58c1fc73fbff734d987495a982508","datavalue":{"value":{"entity-type":"item","numeric-id":3757929,"id":"Q3757929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$978C1244-DE04-46FB-9B1B-F326F2355BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$7509C894-9318-4974-88F2-FB09F20796E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a6bb84ed63e3fc8fe28c0599a7a28ad0bb4690b","datavalue":{"value":{"entity-type":"item","numeric-id":3216652,"id":"Q3216652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$7B4258B3-19BD-4041-9B24-6A5FF4096D8C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"084bbbb4df82d594477fd68358151d484447708c","datavalue":{"value":{"entity-type":"item","numeric-id":6482121,"id":"Q6482121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566702$2ACFCE11-ABC5-4B85-9A09-B7AD64A3DB2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"783f27f37c37842ac75d95f3270bc9bb2865bf1d","datavalue":{"value":{"entity-type":"item","numeric-id":3615812,"id":"Q3615812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1272ccadd301c83fda9d4b7592357bddcd2da736","datavalue":{"value":{"amount":"+0.804000198841095","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":"Q1566702$293DA390-FD56-49E2-BA1D-E221F2D240A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a2ddad0ed1504507abb87ba8e44c13b8c795d97","datavalue":{"value":{"entity-type":"item","numeric-id":1856334,"id":"Q1856334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"807fc24044666f9f7030ac26c4bdd04ce0e16f1b","datavalue":{"value":{"amount":"+0.8014761805534363","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":"Q1566702$950E108D-1D15-43AC-AACD-157850B5DDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6154bea8ab72b405576f1c053f4960e4783c5c9d","datavalue":{"value":{"entity-type":"item","numeric-id":4353558,"id":"Q4353558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"807fc24044666f9f7030ac26c4bdd04ce0e16f1b","datavalue":{"value":{"amount":"+0.8014761805534363","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":"Q1566702$041781B6-DF81-445C-9911-515EFB486318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0874f4d378d1f6c708033223e30b475e8fd431b3","datavalue":{"value":{"entity-type":"item","numeric-id":1336623,"id":"Q1336623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0214a9c5bbe0e74aca2388226071ce2c82945df","datavalue":{"value":{"amount":"+0.8014296889305115","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":"Q1566702$CBA14FA8-0128-4E21-A4D8-FCF562FCCA55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3a9da734080354050da04ac53f4a5fab0132651","datavalue":{"value":{"entity-type":"item","numeric-id":807611,"id":"Q807611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe35b0a475f4cfcaafe37cc82fffce3b0b78f6b9","datavalue":{"value":{"amount":"+0.8002493977546692","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":"Q1566702$8294DE09-347A-41FA-9CF7-67C91F0D391F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The monadic second-order logic of graphs. XII: Planar graphs and planar maps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_monadic_second-order_logic_of_graphs._XII:_Planar_graphs_and_planar_maps"}}}}}