{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:51:06Z","timestamp":1765176666654,"version":"3.46.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:00:00Z","timestamp":1762905600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:00:00Z","timestamp":1762905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00373-025-02990-x","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T10:22:19Z","timestamp":1762942939000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the d-independence number in 1-planar graphs"],"prefix":"10.1007","volume":"41","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[]},{"given":"Babak","family":"Miraftab","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"issue":"1","key":"2990_CR1","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0095-8956(76)90071-X","volume":"20","author":"MO Albertson","year":"1976","unstructured":"Albertson, M.O.: A lower bound for the independence number of a planar graph. Journal of Combinatorial Theory, Series B 20(1), 84\u201393 (1976)","journal-title":"Journal of Combinatorial Theory, Series B"},{"doi-asserted-by":"crossref","unstructured":"Alekseev, V.E., Lozin, V.V., Malyshev D.S., M. Martin.: The maximum independent set problem in planar graphs. In Proc. MFCS, volume 5162 of Lecture Notes in Computer Science, pages 96\u2013107. Springer, (2008)","key":"2990_CR2","DOI":"10.1007\/978-3-540-85238-4_7"},{"key":"2990_CR3","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/098","volume-title":"Every Planar Map is Four Colorable","author":"K Appel","year":"1989","unstructured":"Appel, K., Haken, W.: Every Planar Map is Four Colorable. American Mathematical Society, Providence, RI (1989)"},{"issue":"1","key":"2990_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"2990_CR5","volume-title":"Graphes et hypergraphes","author":"C Berge","year":"1970","unstructured":"Berge, C.: Graphes et hypergraphes. Dunod, Paris (1970)"},{"doi-asserted-by":"crossref","unstructured":"Biedl, T., Bose, P., Miraftab, B.: On the independence number of 1-planar graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, (2024)","key":"2990_CR6","DOI":"10.1007\/s00373-025-02990-x"},{"issue":"3","key":"2990_CR7","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00224-005-1139-0","volume":"38","author":"T Biedl","year":"2005","unstructured":"Biedl, T., Wilkinson, D.F.: Bounded-degree independent sets in planar graphs. Theory Comput. Syst. 38(3), 253\u2013278 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"2990_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.22736","volume":"99","author":"T Biedl","year":"2022","unstructured":"Biedl, T., Wittnebel, J.: Matchings in 1-planar graphs with large minimum degree. J. Graph Theory 99(2), 217\u2013320 (2022)","journal-title":"J. Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Rainer Bodendiek, H., Schumacher, Wagner, K.: \u00dcber 1-optimale graphen. Mathematische Nachrichten 117(1), 323\u2013339 (1984)","key":"2990_CR9","DOI":"10.1002\/mana.3211170125"},{"doi-asserted-by":"crossref","unstructured":"Adrian Bondy, J., Murty, U.S.\u00a0R.: Graph Theory. Graduate Texts in Mathematics. Springer, (2008)","key":"2990_CR10","DOI":"10.1007\/978-1-84628-970-5"},{"issue":"5","key":"2990_CR11","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/21M142188X","volume":"53","author":"\u00c9douard Bonnet","year":"2024","unstructured":"Bonnet, \u00c9douard., Geniet, Colin, Kim, Eun Jung, Thomass\u00e9, St\u00e9phan., Watrigant, R\u00e9mi.: Twin-width III: max independent set, min dominating set, and coloring. SIAM J. Comput. 53(5), 1602\u20131640 (2024)","journal-title":"SIAM J. Comput."},{"issue":"12\u201326","key":"2990_CR12","first-page":"108","volume":"41","author":"OV Borodin","year":"1984","unstructured":"Borodin, O.V.: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of $$1$$-planar graphs. Metody Diskret. Analiz. 41(12\u201326), 108 (1984)","journal-title":"Metody Diskret. Analiz."},{"issue":"1","key":"2990_CR13","doi-asserted-by":"publisher","first-page":"88","DOI":"10.55016\/ojs\/cdm.v1i1.61915","volume":"1","author":"P Bose","year":"2006","unstructured":"Bose, P., Dujmovi\u0107, V., Wood, D.R.: Induced subgraphs of bounded degree and bounded treewidth. Contrib. Discrete Math. 1(1), 88\u2013105 (2006)","journal-title":"Contrib. Discrete Math."},{"issue":"3","key":"2990_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1002\/net.3230190307","volume":"19","author":"JE Burns","year":"1989","unstructured":"Burns, J.E.: The maximum independent set problem for cubic planar graphs. Networks 19(3), 373\u2013378 (1989)","journal-title":"Networks"},{"key":"2990_CR15","first-page":"167","volume":"20","author":"Y Caro","year":"1985","unstructured":"Caro, Y., Roditty, Y.: On the vertex-independence number and star decomposition of graphs. Ars Combin. 20, 167\u2013180 (1985)","journal-title":"Ars Combin."},{"issue":"1","key":"2990_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-011-1040-3","volume":"28","author":"M Chellali","year":"2012","unstructured":"Chellali, M., Favaron, O., Hansberg, A., Volkmann, L.: $$k$$-domination and $$k$$-independence in graphs: A survey. Graphs Comb. 28(1), 1\u201355 (2012)","journal-title":"Graphs Comb."},{"issue":"3","key":"2990_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00453-004-1134-x","volume":"43","author":"Z-Z Chen","year":"2005","unstructured":"Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica 43(3), 147\u2013177 (2005)","journal-title":"Algorithmica"},{"issue":"2","key":"2990_CR18","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230130209","volume":"13","author":"N Chiba","year":"1983","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: An algorithm for finding a large independent set in planar graphs. Networks 13(2), 247\u2013252 (1983)","journal-title":"Networks"},{"issue":"6","key":"2990_CR19","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/BF01759072","volume":"6","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Naor, J.: An efficient parallel algorithm for computing a large independent set in planar graph. Algorithmica 6(6), 801\u2013815 (1991)","journal-title":"Algorithmica"},{"issue":"3","key":"2990_CR20","first-page":"3","volume":"23","author":"DW Cranston","year":"2016","unstructured":"Cranston, D.W., Rabern, L.: Planar graphs have independence ratio at least 3\/13. Electron. J. Comb. 23(3), 3 (2016)","journal-title":"Electron. J. Comb."},{"key":"2990_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jda.2011.12.012","volume":"14","author":"K Dabrowski","year":"2012","unstructured":"Dabrowski, K., Lozin, V., M\u00fcller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207\u2013213 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"1\u20132","key":"2990_CR22","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(90)90130-5","volume":"27","author":"N Dadoun","year":"1990","unstructured":"Dadoun, N., Kirkpatrick, D.G.: Parallel algorithms for fractional and maximal independent sets in planar graphs. Discret. Appl. Math. 27(1\u20132), 69\u201383 (1990)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2990_CR23","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"DP Dobkin","year":"1985","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381\u2013392 (1985)","journal-title":"J. Algorithms"},{"issue":"2","key":"2990_CR24","doi-asserted-by":"publisher","first-page":"1355","DOI":"10.1137\/16M1061862","volume":"31","author":"Z Dvor\u00e1k","year":"2017","unstructured":"Dvor\u00e1k, Z., Mnich, M.: Large independent sets in triangle-free planar graphs. SIAM J. Discret. Math. 31(2), 1355\u20131373 (2017)","journal-title":"SIAM J. Discret. Math."},{"doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Pavel, Feldmann, Andreas Emil, Rai, Ashutosh, Pawe\u0142Rz\u0105\u017cewski.: Parameterized inapproximability of independent set in $$H$$-free graphs. Algorithmica 85(4), 902\u2013928 (2023)","key":"2990_CR25","DOI":"10.1007\/s00453-022-01052-5"},{"unstructured":"Fomin, F.V., Golovach, P.A., Sagunov, D., Simonov. Kirill.: Hamiltonicity, path cover, and independence number: An FPT perspective. arXiv:2403.05943, (2024)","key":"2990_CR26"},{"issue":"3","key":"2990_CR27","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"2990_CR28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0304-3975(88)90106-5","volume":"61","author":"X He","year":"1988","unstructured":"He, X.: A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs. Theor. Comput. Sci. 61, 33\u201347 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"2990_CR29","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s10958-014-1690-9","volume":"196","author":"Dmitri V Karpov","year":"2014","unstructured":"Karpov, Dmitri V.: An upper bound on the number of edges in an almost planar bipartite graph. Journal of Mathematical Sciences 196, 737\u2013746 (2014)","journal-title":"Journal of Mathematical Sciences"},{"issue":"1","key":"2990_CR30","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in p 5-free graphs in polynomial time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, pages 570\u2013581. SIAM, (2014)","key":"2990_CR31","DOI":"10.1137\/1.9781611973402.43"},{"issue":"2","key":"2990_CR32","doi-asserted-by":"publisher","first-page":"269","DOI":"10.7155\/jgaa.00207","volume":"14","author":"VV Lozin","year":"2010","unstructured":"Lozin, V.V., Milanic, M.: On the maximum independent set problem in subclasses of planar graphs. J. Graph Algorithms Appl. 14(2), 269\u2013286 (2010)","journal-title":"J. Graph Algorithms Appl."},{"doi-asserted-by":"crossref","unstructured":"Veni Madhavan C.\u00a0E.: Approximation algorithm for maximum independent set in planar traingle-free graphs. In Proc. FSTTCS, volume 181 of Lecture Notes in Computer Science, pages 381\u2013392. Springer, (1984)","key":"2990_CR33","DOI":"10.1007\/3-540-13883-8_86"},{"doi-asserted-by":"crossref","unstructured":"Magen, A., Moharrami, M.: Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In Proc. APPROX, volume 5687 of Lecture Notes in Computer Science, pages 258\u2013271. Springer, (2009)","key":"2990_CR34","DOI":"10.1007\/978-3-642-03685-9_20"},{"issue":"1","key":"2990_CR35","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"Bojan Mohar","year":"2001","unstructured":"Mohar, Bojan: Face covers and the genus problem for apex graphs. J. Comb. Theory Ser. B 82(1), 102\u2013117 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"2990_CR36","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"Neil Robertson","year":"1997","unstructured":"Robertson, Neil, Sanders, Daniel P., Seymour, Paul, Thomas, Robin: The four-colour theorem. J. Comb. Theory Ser. B 70(1), 2\u201344 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"doi-asserted-by":"crossref","unstructured":"Schaefer, Marcus.: The graph crossing number and its variants: a survey. Electron. J. Combin., DS21:90, (2013)","key":"2990_CR37","DOI":"10.37236\/2713"},{"key":"2990_CR38","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/mana.19861250122","volume":"125","author":"H Schumacher","year":"1986","unstructured":"Schumacher, H.: Zur Struktur 1-planarer Graphen. Math. Nachr. 125, 291\u2013300 (1986)","journal-title":"Math. Nachr."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02990-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02990-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02990-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T03:20:19Z","timestamp":1765164019000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02990-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,12]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2990"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02990-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,11,12]]},"assertion":[{"value":"5 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors disclosed no relevant relationships.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"127"}}