{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:45:26Z","timestamp":1767314726131,"version":"3.48.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-11835-6_15","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:42:23Z","timestamp":1767314543000},"page":"205-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Segment Intersection Representations, Level Planarity and\u00a0Constrained Ordering Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2754-1195","authenticated-orcid":false,"given":"Simon D.","family":"Fink","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5378-1694","authenticated-orcid":false,"given":"Matthias","family":"Pfretzschner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0531-9769","authenticated-orcid":false,"given":"Peter","family":"Stumpf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/J.TCS.2019.11.024","volume":"804","author":"P Angelini","year":"2020","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity: cyclic, torus, and simultaneous level planarity. Theoret. Comput. Sci. 804, 161\u2013170 (2020). https:\/\/doi.org\/10.1016\/J.TCS.2019.11.024","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-662-45803-7_21","volume-title":"Graph Drawing","author":"P Angelini","year":"2014","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 246\u2013258. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_21"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.TCS.2014.12.019","volume":"571","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper: (in clustered-level planarity and t-level planarity). Theor. Comput. Sci. 571, 1\u20139 (2015). https:\/\/doi.org\/10.1016\/J.TCS.2014.12.019","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"15_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(93)90354-V","volume":"114","author":"S Bellantoni","year":"1993","unstructured":"Bellantoni, S., Ben-Arroyo Hartman, I., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity. Discret. Math. 114(1), 41\u201349 (1993). https:\/\/doi.org\/10.1016\/0012-365X(93)90354-V","journal-title":"Discret. Math."},{"key":"15_CR5","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), 16:1\u201316:46 (2016). https:\/\/doi.org\/10.1145\/2738054","DOI":"10.1145\/2738054"},{"key":"15_CR6","unstructured":"Booth, K.S.: PQ-tree algorithms. Ph.D. thesis, University of California, Berkeley (1975)"},{"issue":"3","key":"15_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-030-04414-5_3","volume-title":"Graph Drawing and Network Visualization","author":"G Br\u00fcckner","year":"2018","unstructured":"Br\u00fcckner, G., Rutter, I., Stumpf, P.: Level planarity: transitivity vs. even crossings. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 39\u201352. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_3"},{"key":"15_CR9","doi-asserted-by":"publisher","unstructured":"Br\u00fcckner, G., Rutter, I., Stumpf, P.: Level-planarity: transitivity vs. even crossings. Electron. J. Combin. 29(4) (2022). https:\/\/doi.org\/10.37236\/10814","DOI":"10.37236\/10814"},{"key":"15_CR10","doi-asserted-by":"publisher","unstructured":"Fulek, R., Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Hanani-Tutte, monotone drawings, and level-planarity. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 263\u2013287. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-0110-0_14","DOI":"10.1007\/978-1-4614-0110-0_14"},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"IBA Hartman","year":"1991","unstructured":"Hartman, I.B.A., Newman, I., Ziv, R.: On grid intersection graphs. Discret. Math. 87(1), 41\u201352 (1991). https:\/\/doi.org\/10.1016\/0012-365X(91)90069-E","journal-title":"Discret. Math."},{"issue":"1","key":"15_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.7155\/jgaa.00045","volume":"6","author":"M J\u00fcnger","year":"2002","unstructured":"J\u00fcnger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 67\u2013113 (2002). https:\/\/doi.org\/10.7155\/jgaa.00045","journal-title":"J. Graph Algorithms Appl."},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-37623-2_17","volume-title":"Graph Drawing","author":"M J\u00fcnger","year":"1998","unstructured":"J\u00fcnger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224\u2013237. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-37623-2_17"},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its np-completeness. Discret. Appl. Math. 52(3), 233\u2013252 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90143-0","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62(2), 289\u2013315 (1994). https:\/\/doi.org\/10.1006\/jctb.1994.1071","journal-title":"J. Combin. Theory Ser. B"},{"key":"15_CR16","doi-asserted-by":"publisher","unstructured":"Kratochv\u00edl, J., Nesetril, J.: Problems proposed at the problem session of the prachatice conference on graph theory. In: Nesetril, J., Fiedler, M. (eds.) Proceeding of the Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity. Annals of Discrete Mathematics, vol.\u00a051, pp. 375\u2013384. Elsevier (1992). https:\/\/doi.org\/10.1016\/S0167-5060(08)70659-9","DOI":"10.1016\/S0167-5060(08)70659-9"},{"key":"15_CR17","doi-asserted-by":"publisher","unstructured":"Kratochv\u00edl, J.: String graphs. II. Recognizing string graphs is NP-hard. J. Combin. Theory Ser. B 52(1), 67\u201378 (1991). https:\/\/doi.org\/10.1016\/0095-8956(91)90091-W","DOI":"10.1016\/0095-8956(91)90091-W"},{"key":"15_CR18","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: NP-hardness results for intersection graphs. Commentationes Math. Univ. Carolinae 030(4), 761\u2013773 (1989). https:\/\/eudml.org\/doc\/17790"},{"issue":"1","key":"15_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979). https:\/\/doi.org\/10.1137\/0208008","journal-title":"SIAM J. Comput."},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S1571-0653(04)00327-0","volume":"9","author":"B Randerath","year":"2001","unstructured":"Randerath, B., et al.: A satisfiability formulation of problems on level graphs. Electron. Notes Discrete Math. 9, 269\u2013277 (2001). https:\/\/doi.org\/10.1016\/S1571-0653(04)00327-0","journal-title":"Electron. Notes Discrete Math."},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11805-0_32"},{"issue":"4","key":"15_CR22","doi-asserted-by":"publisher","first-page":"367","DOI":"10.7155\/jgaa.00298","volume":"17","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367\u2013440 (2013). https:\/\/doi.org\/10.7155\/jgaa.00298","journal-title":"J. Graph Algorithms Appl."},{"issue":"16\u201317","key":"15_CR23","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1016\/J.DAM.2012.05.028","volume":"160","author":"A Wotzlaw","year":"2012","unstructured":"Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized k-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation. Discret. Appl. Math. 160(16\u201317), 2349\u20132363 (2012). https:\/\/doi.org\/10.1016\/J.DAM.2012.05.028","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:42:24Z","timestamp":1767314544000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}