{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T08:19:34Z","timestamp":1743063574158,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319272603"},{"type":"electronic","value":"9783319272610"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-27261-0_33","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T06:24:59Z","timestamp":1448519099000},"page":"395-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Embeddability of Buses in Point Sets"],"prefix":"10.1007","author":[{"given":"Till","family":"Bruckdorfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen G.","family":"Kobourov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"key":"33_CR1","unstructured":"Ada, A., Coggan, M., Marco, P.D., Doyon, A., Flookes, L., Heilala, S., Kim, E., Wing, J.L.O., Pr\u00e9ville-Ratelle, L.F., Whitesides, S., Yu, N.: On bus graph realizability. In: Canadian Conference on Computational Geometry, pp. 229\u2013232 (2007)"},{"issue":"12","key":"33_CR2","doi-asserted-by":"publisher","first-page":"2259","DOI":"10.1109\/TVCG.2011.186","volume":"17","author":"B Alper","year":"2011","unstructured":"Alper, B., Riche, N.H., Ramos, G., Czerwinski, M.: Design study of LineSets, a novel set visualization technique. IEEE Trans. Visual. Comput. Graph. 17(12), 2259\u20132267 (2011)","journal-title":"IEEE Trans. Visual. Comput. Graph."},{"issue":"3","key":"33_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inform. Process. Lett."},{"key":"33_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-319-03841-4_22","volume-title":"Graph Drawing","author":"MA Bekos","year":"2013","unstructured":"Bekos, M.A., Cornelsen, S., Fink, M., Hong, S.-H., Kaufmann, M., N\u00f6llenburg, M., Rutter, I., Symvonis, A.: Many-to-one boundary labeling with backbones. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 244\u2013255. Springer, Heidelberg (2013)"},{"issue":"2","key":"33_CR5","doi-asserted-by":"crossref","first-page":"16","DOI":"10.37236\/1688","volume":"9","author":"M B\u00f3na","year":"2003","unstructured":"B\u00f3na, M.: A survey of stack-sorting disciplines. Electron. J. Comb. 9(2), 16 (2003)","journal-title":"Electron. J. Comb."},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-38233-8_7","volume-title":"Algorithms and Complexity","author":"T Bruckdorfer","year":"2013","unstructured":"Bruckdorfer, T., Felsner, S., Kaufmann, M.: On the characterization of plane bus graphs. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 73\u201384. Springer, Heidelberg (2013)"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Bruckdorfer, T., Kaufmann, M., Kobourov, S., Pupyrev, S.: On embeddability of buses in point sets. CoRR abs\/1508.06760 (2015)","DOI":"10.1007\/978-3-319-27261-0_33"},{"issue":"4","key":"33_CR8","doi-asserted-by":"publisher","first-page":"533","DOI":"10.7155\/jgaa.00237","volume":"15","author":"K Buchin","year":"2011","unstructured":"Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533\u2013549 (2011)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"33_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.7155\/jgaa.00132","volume":"10","author":"S Cabello","year":"2006","unstructured":"Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353\u2013366 (2006)","journal-title":"J. Graph Algorithms Appl."},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Chen, H., Qiao, C., Zhou, F., Cheng, C.K.: Refined single trunk tree: A rectilinear Steiner tree generator for interconnect prediction. In: SLIP, pp. 85\u201389. ACM (2002)","DOI":"10.1145\/505348.505366"},{"issue":"6","key":"33_CR11","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1109\/TVCG.2009.122","volume":"15","author":"C Collins","year":"2009","unstructured":"Collins, C., Penn, G., Carpendale, T.: Bubble Sets: Revealing set relations with isocontours over existing visualizations. IEEE Trans. Visual. Comput. Graph. 15(6), 1009\u20131016 (2009)","journal-title":"IEEE Trans. Visual. Comput. Graph."},{"issue":"1","key":"33_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.7155\/jgaa.00099","volume":"9","author":"M Dickerson","year":"2005","unstructured":"Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 31\u201352 (2005)","journal-title":"J. Graph Algorithms Appl."},{"key":"33_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/978-3-662-45803-7_38","volume-title":"Graph Drawing","author":"A Efrat","year":"2014","unstructured":"Efrat, A., Hu, Y., Kobourov, S.G., Pupyrev, S.: MapSets: visualizing embedded and clustered graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 452\u2013463. Springer, Heidelberg (2014)"},{"key":"33_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-540-70904-6_37","volume-title":"Graph Drawing","author":"ER Gansner","year":"2007","unstructured":"Gansner, E.R., Koren, Y.: Improved circular layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386\u2013398. Springer, Heidelberg (2007)"},{"issue":"4","key":"33_CR15","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"33_CR16","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"33_CR17","unstructured":"Gurobi Optimization, I.: Gurobi optimizer reference manual (2015). www.gurobi.com"},{"key":"33_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-03841-4_25","volume-title":"Graph Drawing","author":"F Hurtado","year":"2013","unstructured":"Hurtado, F., Korman, M., van Kreveld, M., L\u00f6ffler, M., Sacrist\u00e1n, V., Silveira, R.I., Speckmann, B.: Colored spanning graphs for set visualization. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 280\u2013291. Springer, Heidelberg (2013)"},{"key":"33_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-11805-0_21","volume-title":"Graph Drawing","author":"B Katz","year":"2010","unstructured":"Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic embedding of planar graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207\u2013218. Springer, Heidelberg (2010)"},{"key":"33_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-319-08404-6_23","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"B Klemz","year":"2014","unstructured":"Klemz, B., Mchedlidze, T., N\u00f6llenburg, M.: Minimum tree supports for hypergraphs and low-concurrency euler diagrams. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 265\u2013276. Springer, Heidelberg (2014)"},{"key":"33_CR21","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming, Volume 1","author":"DE Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 1. Fundamental Algorithms, 3rd edn. Addison Wesley Longman Publishing Co., Inc., Redwood (1997)","edition":"3"},{"key":"33_CR22","first-page":"835","volume-title":"Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A)","author":"T Lengauer","year":"1990","unstructured":"Lengauer, T.: VLSI theory. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 835\u2013868. Elsevier, Amsterdam (1990)"},{"issue":"2","key":"33_CR23","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"33_CR24","doi-asserted-by":"publisher","first-page":"1846","DOI":"10.1109\/TVCG.2013.76","volume":"19","author":"W Meulemans","year":"2013","unstructured":"Meulemans, W., Riche, N.H., Speckmann, B., Alper, B., Dwyer, T.: KelpFusion: A hybrid set visualization technique. IEEE Trans. Visual. Comput. Graph. 19(11), 1846\u20131858 (2013)","journal-title":"IEEE Trans. Visual. Comput. Graph."},{"key":"33_CR25","unstructured":"Pierrot, A., Rossin, D.: 2-stack pushall sortable permutations. CoRR abs\/1303.4376 (2013)"},{"key":"33_CR26","unstructured":"Pierrot, A., Rossin, D.: 2-stack sorting is polynomial. In: Mayr, E.W., Portier, N. (eds.) Symposium on Theoretical Aspects of Computer Science. LIPIcs, vol. 25, pp. 614\u2013626. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"6","key":"33_CR27","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1109\/TVCG.2010.210","volume":"16","author":"NH Riche","year":"2010","unstructured":"Riche, N.H., Dwyer, T.: Untangling Euler diagrams. IEEE Trans. Visual. Comput. Graph. 16(6), 1090\u20131099 (2010)","journal-title":"IEEE Trans. Visual. Comput. Graph."},{"issue":"3","key":"33_CR28","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1111\/j.1467-8659.2009.01452.x","volume":"28","author":"P Simonetto","year":"2009","unstructured":"Simonetto, P., Auber, D., Archambault, D.: Fully automatic visualisation of overlapping sets. Comput. Graph. Forum 28(3), 967\u2013974 (2009)","journal-title":"Comput. Graph. Forum"},{"key":"33_CR29","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-27261-0_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T22:49:00Z","timestamp":1599864540000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-27261-0_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319272603","9783319272610"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-27261-0_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 November 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}