{"entities":{"Q1856334":{"pageid":1867076,"ns":120,"title":"Item:Q1856334","lastrevid":71001297,"modified":"2026-04-13T18:49:34Z","type":"item","id":"Q1856334","labels":{"en":{"language":"en","value":"Map genus, forbidden maps, and monadic second-order logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1862485"}},"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":"Q1856334$5E2F04E4-217B-433B-AA48-65B33CBCA724","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e22a3442b8c7e52bd3dfd39e7e7c4abab11dd7f3","datavalue":{"value":{"text":"Map genus, forbidden maps, and monadic second-order logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1856334$08380A37-2C50-4607-8440-6D0FCD54FD79","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b537facbceadd7a78f705a899e08a4b25d4e8b3","datavalue":{"value":"1016.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856334$19B1D250-03B7-4C4C-8D8B-18F8B84F3B58","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4146c7c6c4e4945cc5d3cbe49da8035f16f197b1","datavalue":{"value":{"entity-type":"item","numeric-id":1856333,"id":"Q1856333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856334$18A4262D-38E7-4EE1-9F8A-7AACB23590FB","rank":"normal"},{"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":"Q1856334$D344DF1C-1C22-4E72-86A0-3216CC2A4956","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856334$41F44D4C-A716-4E02-AC7C-04E6190600D0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"111dc11587271f29bffc5b4de8ed3b84d4c073f3","datavalue":{"value":{"time":"+2003-05-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":"Q1856334$2CCF370A-BBE5-4D6D-90B8-4C45EC44F8E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d0fd9e3efccc3927524f278dd007f27008fe3d8","datavalue":{"value":"https://eudml.org/doc/122754","type":"string"},"datatype":"url"},"type":"statement","id":"Q1856334$967ED30F-5291-4AAF-BC3F-67E99368FCB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"734a28eff7bc803bdf94ea864517bc119ec121ee","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r40.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1856334$D4ACBEF2-7455-46AC-ACAB-F3B72ADFCC03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e05de7206e58c1589e936f84a7eff9359c0706c","datavalue":{"value":"Graphs can be described in terms of a binary edge-relation, and so can be expressed as a logical formula. These formulas cannot express some basic graph-theoretic properties in first-order logic. Second-order logic allows new variables denoting relations and are subject to quantification, and many graph-theoretic properties can be expressed in second-order logic. Monadic second-order logic lies between first- and second-order logic; it allows set variables but no variables denoting binary relations or relations of larger arity.    A map is a graph together with, for each vertex, a cyclic permutation of the edges incident with that vertex. Maps describe embeddings of the graph into oriented surfaces; these surfaces are characterized in terms of a non-negative integer called their genus. Maps that embed on a surface of genus at most \\(g\\) are characterized in terms of a finite number of forbidden submaps. This characterization gives the existence of the embedding, but does not specify the particular embedding.    In this paper the authors give a different characterization of graphs that, in addition to stating its existence, specifies the relevant surface embedding. This characterization is expressible in monadic second-order logic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856334$DBF55D76-A394-48F3-B9CB-81259EEE4774","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856334$B31D9503-B9CB-4C31-A6F2-5D154678A091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856334$017229F6-AB74-4102-A7A4-C13F57B0AFA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64fda04e707cebc66c521bfd9de309294422cbee","datavalue":{"value":"1862485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856334$DA83C138-1D81-4138-9455-B9228A590E2F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856334$C4C2254B-41AE-4D5E-9191-63D1AD100CC5","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":"Q1856334$994B7621-854E-40E9-852D-B5F75B0D9B06","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9053a0c809dcb3d42d8a0a3184b6eaae998cc099","datavalue":{"value":"bafkreicxjhiawjpjg5yikd4twdhweuhsi3kqrpvhwfntteg5eujystzbti","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856334$98A611BF-8949-47F1-A2A0-3ECEA5F0AA5C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3757eaa18d0c698ba5f0513ab9524aca4c79472d","datavalue":{"value":{"entity-type":"item","numeric-id":1566702,"id":"Q1566702"},"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":"Q1856334$DE770965-A610-4BAF-BEBC-315540C61899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a18c0da6d5262263a5d0f4c34c0747b2f251b9d","datavalue":{"value":{"entity-type":"item","numeric-id":1352472,"id":"Q1352472"},"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":"Q1856334$756F18C1-B434-4592-86B9-B7B3F59350DD","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":"a2fbd6bb5872a53a118d8c611bd454ed39303a11","datavalue":{"value":{"amount":"+0.7524694204330444","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":"Q1856334$2BE8352B-4661-44C4-841B-48D28E1AC265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f82e8dcaed93dba4d50de2ad581b99883aa343c","datavalue":{"value":{"entity-type":"item","numeric-id":5002801,"id":"Q5002801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90337cafc357aacfbb6f1b5826d3d80d1cae5aa5","datavalue":{"value":{"amount":"+0.7497092485427856","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":"Q1856334$B1BC8983-8C2B-4D75-8D15-F90513AA297D","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":"d26d15703bd6142ab10193b9bb47de33603e4c35","datavalue":{"value":{"amount":"+0.7350513935089111","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":"Q1856334$8ED89200-518A-4B7E-9EA1-8E1616892C81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Map genus, forbidden maps, and monadic second-order logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Map_genus,_forbidden_maps,_and_monadic_second-order_logic"}}}}}