{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:40:33Z","timestamp":1725489633544},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540656913"},{"type":"electronic","value":"9783540491163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49116-3_2","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:56:14Z","timestamp":1187268974000},"page":"16-31","source":"Crossref","is-referenced-by-count":0,"title":["The Reduced Genus of a Multigraph"],"prefix":"10.1007","author":[{"given":"Patrice Ossona","family":"de Mendez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,4,12]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel and W. Haken. Every planar map is four colorable. part I. discharging. Illinois J. Math., 21:429\u2013490, 1977.","journal-title":"Illinois J. Math."},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. part II. reducibility. Illinois J. Math., 21:491\u2013567, 1977.","journal-title":"Illinois J. Math."},{"key":"2_CR3","unstructured":"C. Berge. Graphes et hypergraphes. Dunod, Paris, second edition, 1973."},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1112\/jlms\/s1-44.1.612","volume":"44","author":"G. Chartrand","year":"1969","unstructured":"G. Chartrand and H.V. Kronk. The point arboricity of planar graphs. J. Lond. Math. Soc., 44:612\u2013616, 1969.","journal-title":"J. Lond. Math. Soc."},{"key":"2_CR5","volume-title":"Un code pour les graphes planaires et ses applications","author":"R. Cori","year":"1975","unstructured":"R. Cori. Un code pour les graphes planaires et ses applications, volume 27. Soci\u00e9t\u00e9 math\u00e9matique de france, Paris, 1975."},{"key":"2_CR6","unstructured":"H. de Fraysseix and P. Ossona de Mendez. Intersection graphs of Jordan arcs. In Stirin 1997 Proc. DIMATIA-DIMACS. (accepted)."},{"key":"2_CR7","unstructured":"H. de Fraysseix and P. Ossona de Mendez. Stretchability of Jordan arc contact systems. Technical Report 98-387, KAM-DIMATIA Series, 1998."},{"key":"2_CR8","first-page":"109","volume":"63","author":"H. Fraysseix de","year":"1991","unstructured":"H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109\u2013117, 1991.","journal-title":"Intuitive Geometry"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0963548300001139","volume":"3","author":"H. Fraysseix de","year":"1994","unstructured":"H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233\u2013246, 1994.","journal-title":"Combinatorics, Probability and Computing"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"352","DOI":"10.2307\/2307489","volume":"61","author":"B. Descartes","year":"1954","unstructured":"B. Descartes. Solution to advanced problem no. 4256. Am. Math. Mon., 61:352, 1954.","journal-title":"Am. Math. Mon."},{"key":"2_CR11","first-page":"125","volume":"XXVI","author":"P. Erd\u00f6s","year":"1979","unstructured":"P. Erd\u00f6s, A.L. Rubin, and H. Taylor. Choosability in graphs. In Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing, volume XXVI, pages 125\u2013157, Arcata, California, 1979.","journal-title":"Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing"},{"key":"2_CR12","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"I. F\u00e1ry. On straight line representation of planar graphs. Acta Scientiarum Mathematicarum Szeged), 11:229\u2013233, 1948.","journal-title":"Acta Scientiarum Mathematicarum Szeged)"},{"key":"2_CR13","first-page":"109","volume":"8","author":"H. Gr\u00f6tzsch","year":"1958","unstructured":"H. Gr\u00f6tzsch. Ein Dreifarbensatz f\u00fcr dreikreisfrei Netze auf der Kugel. Wissenchaftliche Zeitschrift der Martin-Luther-Universit\u00e4t Halle-Wittenberg. Mathematisch-Naturwissenschaftliche Reihe, 8:109\u2013120, 1958\/1959.","journal-title":"Wissenchaftliche Zeitschrift der Martin-Luther-Universit\u00e4t Halle-Wittenberg. Mathematisch-Naturwissenschaftliche Reihe"},{"key":"2_CR14","first-page":"332","volume":"24","author":"P.J. Heawood","year":"1890","unstructured":"P.J. Heawood. Map color theorem. Q.J. Pure Appl. Math., 24:332\u2013338, 1890.","journal-title":"Q.J. Pure Appl. Math."},{"key":"2_CR15","volume-title":"Hochschulskriptum 8 10\/a\/b","author":"H. Heesch","year":"1969","unstructured":"H. Heesch. Untersuchungen zum Vierfarbenproblem. Hochschulskriptum 8 10\/a\/b, Bibliographisches Institut, Mannheim, 1969."},{"issue":"3","key":"2_CR16","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/jgt.3190110306","volume":"11","author":"D.S. Johnson","year":"1987","unstructured":"D.S. Johnson and H.O. Pollak. Hypergraph planarity and the complexity of drawing Venn diagrams. Journal of Graph Theory, 11(3):309\u2013325, 1987.","journal-title":"Journal of Graph Theory"},{"key":"2_CR17","series-title":"PhD thesis","volume-title":"Colourings of Hypergraphs","author":"R.P. Jones","year":"1976","unstructured":"R.P. Jones. Colourings of Hypergraphs. PhD thesis, Royal Holloway College, Egham, 1976."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"786","DOI":"10.2307\/2372652","volume":"76","author":"J.B. Kelly","year":"1954","unstructured":"J.B. Kelly and L.M. Kelly. Paths and circuits in critical graphs. Am. J. Math., 76:786\u2013792, 1954.","journal-title":"Am. J. Math."},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01894680","volume":"19","author":"L. Lovasz","year":"1968","unstructured":"L. Lovasz. On chromatic numbers of finite set systems. Acta Math. Acad. Sci. Hung., 19:59\u201367, 1968.","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"B. Mohar and P. Rosenstiehl. A flow approach to upward drawings of toroidal maps. In proc. of Graph Drawing\u2019 94, pages 33\u201339, 1995.","DOI":"10.1007\/3-540-58950-3_354"},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J. Mycielski","year":"1955","unstructured":"J. Mycielski. Sur le coloriage des graphes. Colloq. Math., 3:161\u2013162, 1955.","journal-title":"Colloq. Math."},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"G. Ringel and J.W.T. Youngs. Solution of the Heawood map coloring problem. volume 60 of Proc. Nat. Acad. Sci., pages 438\u2013445, 1968.","DOI":"10.1073\/pnas.60.2.438"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1090\/S1079-6762-96-00003-0","volume":"2","author":"N. Robertson","year":"1996","unstructured":"N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas. A new proof of the four color theorem. Electron. Res. Announc. Amer. Math. Soc., 2:17\u201325, 1996. (electronic).","journal-title":"Electron. Res. Announc. Amer. Math. Soc."},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas. The four color theorem. J. Comb Theory, B(70):2\u201344, 1997.","journal-title":"J. Comb Theory"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layout and bipolar orientation of planar graphs. Discrete and Computational Geometry, 1:343\u2013353, 1986.","journal-title":"Discrete and Computational Geometry"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"464","DOI":"10.2307\/2031777","volume":"2","author":"S.K. Stein","year":"1951","unstructured":"S.K. Stein. Convex maps. In Proc. Amer. Math. Soc., volume 2, pages 464\u2013466, 1951.","journal-title":"Proc. Amer. Math. Soc."},{"key":"2_CR27","volume-title":"Vorlesung \u00fcber die Theorie der Polyeder","author":"E. Steinitz","year":"1934","unstructured":"E. Steinitz and H. Rademacher. Vorlesung \u00fcber die Theorie der Polyeder. Springer, Berlin, 1934."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G. Szekeres","year":"1968","unstructured":"G. Szekeres and H.S. Wilf. An inequality for the chromatic number of a graph. J. Comb. Theory, 4:1\u20133, 1968.","journal-title":"J. Comb. Theory"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jctb.1994.1062","volume":"62","author":"C. Thomassen","year":"1994","unstructured":"C. Thomassen. Every planar graph is 5-choosable. Journal of Combinatorial Theory, B(62):180\u2013181, 1994.","journal-title":"Journal of Combinatorial Theory"},{"key":"2_CR30","first-page":"3","volume":"29","author":"V.G. Vizing","year":"1976","unstructured":"V.G. Vizing. Coloring the vertices of a graph in prescribed colors. Mtody Diskret. Anal. v Teorii Kodov i Schem, 29:3\u201310, 1976. (In russian).","journal-title":"Mtody Diskret. Anal. v Teorii Kodov i Schem"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0012-365X(94)00180-9","volume":"146","author":"M. Voigt","year":"1995","unstructured":"M. Voigt. A not 3-choosable planar graph without 3-cycles. Discrete Math., 146:325\u2013328, 1995.","journal-title":"Discrete Math."},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<233::AID-JGT4>3.0.CO;2-Q","volume":"24","author":"M. Voigt","year":"1997","unstructured":"M. Voigt and B. Wirth. On 3-colorable non 4-choosable planar graphs. Journal of Graph Theory, 24:233\u2013235, 1997.","journal-title":"Journal of Graph Theory"},{"key":"2_CR33","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"K. Wagner. Bemerkungen zum Vierfarbenproblem. Jber. Deutsch. Math. Verein, 46:26\u201332, 1936.","journal-title":"Jber. Deutsch. Math. Verein"},{"issue":"B","key":"2_CR34","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0095-8956(75)90042-8","volume":"18","author":"T.R.S. Walsh","year":"1975","unstructured":"T.R.S. Walsh. Hypermaps versus bipartite maps. J. Combinatorial Theory, 18(B):155\u2013163, 1975.","journal-title":"J. Combinatorial Theory"},{"key":"2_CR35","series-title":"Mathematics Studies, chapter 13","first-page":"205","volume-title":"Graphs, Groups and Surfaces","author":"A.T. White","year":"1984","unstructured":"A.T. White. Graphs, Groups and Surfaces, volume 8 of Mathematics Studies, chapter 13, pages 205\u2013210. North-Holland, Amsterdam, revised edition, 1984."},{"key":"2_CR36","first-page":"89","volume":"6","author":"A.A. Zykov","year":"1974","unstructured":"A.A. Zykov. Hypergraphs. Uspeki Mat. Nauk, 6:89\u2013154, 1974.","journal-title":"Uspeki Mat. Nauk"}],"container-title":["Lecture Notes in Computer Science","STACS 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49116-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:43:22Z","timestamp":1556772202000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49116-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656913","9783540491163"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-49116-3_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}