{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T01:39:57Z","timestamp":1648863597136},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T00:00:00Z","timestamp":1494892800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0321-5","type":"journal-article","created":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T14:01:32Z","timestamp":1494943292000},"page":"2260-2285","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Planar Bus Graphs"],"prefix":"10.1007","volume":"80","author":[{"given":"Till","family":"Bruckdorfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Felsner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,16]]},"reference":[{"key":"321_CR1","unstructured":"Ada, A., Coggan, M., Di Marco, P., 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: Proceedings of CCCG, pp. 229\u2013232 (2007)"},{"issue":"1","key":"321_CR2","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1006\/jagm.2000.1132","volume":"38","author":"TC Biedl","year":"2001","unstructured":"Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen\u2019s matching theorem. J. Algorithms 38(1), 110\u2013134 (2001)","journal-title":"J. Algorithms"},{"key":"321_CR3","unstructured":"de\u00a0Fraysseix, H., Ossona de Mendez, P., Pach, J.: Representations of planar graphs by segments. In: Intuitive Geometry (Szeged, 1991), pp. 109\u2013117. Colloq. Math. Soc. J\u00e1nos Bolyai vol.\u00a063 (1994)"},{"key":"321_CR4","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF02574056","volume":"13","author":"H Fraysseix de","year":"1995","unstructured":"de Fraysseix, H., Ossona de Mendez, P., Pach, J.: A left-first search algorithm for planar graphs. Discrete Comput. Geom. 13, 459\u2013468 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"321_CR5","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Ossona de Mendez, P.: On topological aspects of orientations. Discrete Math. 229, 57\u201372 (2001)","DOI":"10.1016\/S0012-365X(00)00201-6"},{"key":"321_CR6","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)"},{"key":"321_CR7","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Tamassia, R.: Incremental planarity testing (extended abstract). In: Proceedings Foundations of Computer Science, pp. 436\u2013441 (1989)","DOI":"10.1109\/SFCS.1989.63515"},{"issue":"4","key":"321_CR8","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"321_CR9","doi-asserted-by":"crossref","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 Alg. Appl. 9(1), 31\u201352 (2005)","journal-title":"J. Graph Alg. Appl."},{"key":"321_CR10","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Planar Lombardi drawings for subcubic graphs. In: Proceedings of Graph Drawing, vol. 7704 of Lecture Notes in Computer Science, pp. 126\u2013137. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-36763-2_12"},{"key":"321_CR11","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays in Geometric Graph Theory, vol.\u00a029 of Algorithms and Combinatorics, pp. 213\u2013248. Springer, Berlin (2012)","DOI":"10.1007\/978-1-4614-0110-0_12"},{"issue":"3","key":"321_CR12","first-page":"115","volume":"12","author":"S Felsner","year":"2010","unstructured":"Felsner, S., Huemer, C., Kappes, S., Orden, D.: Binary labelings for plane quadrangulations and their relatives. Discrete Math. Theor. Comput. Sci. 12(3), 115\u2013138 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"321_CR13","doi-asserted-by":"crossref","unstructured":"Gansner, E.R., Koren, Y.: Improved circular layouts. In: Proceedings of Graph Drawing, vol. 4372 of Lecture Notes in Computer Science, pp. 386\u2013398. Springer, Berlin (2006)","DOI":"10.1007\/978-3-540-70904-6_37"},{"key":"321_CR14","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., J\u00fcnger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: Subgraph induced planar connectivity augmentation. In: Proceedings of Workshop Graph-Theoretic Concepts Computer Science, vol. 2880 of Lecture Notes in Computer Science, pp. 261\u2013272. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-39890-5_23"},{"key":"321_CR15","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Proceedings of Graph Drawing, vol. 1984 of Lecture Notes in Computer Science, pp. 77\u201390. Springer, Berlin (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"key":"321_CR16","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M Hanan","year":"1966","unstructured":"Hanan, M.: On Steiner\u2019s problem with rectilinear distance. SIAM J. Appl. Math 14, 255\u2013265 (1966)","journal-title":"SIAM J. Appl. Math"},{"key":"321_CR17","first-page":"249","volume":"17","author":"F Harary","year":"1967","unstructured":"Harary, F., Plummer, M.: On the core of a graph. Proc. Lond. Math. Soc. 17, 249\u2013257 (1967)","journal-title":"Proc. Lond. Math. Soc."},{"key":"321_CR18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"97","author":"IB-H Hartman","year":"1991","unstructured":"Hartman, I.B.-H., Newman, I., Ziv, R.: On grid intersection graphs. Discrete Math. 97, 41\u201352 (1991)","journal-title":"Discrete Math."},{"key":"321_CR19","doi-asserted-by":"crossref","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X He","year":"1993","unstructured":"He, X.: On finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22, 1218\u20131226 (1993)","journal-title":"SIAM J. Comput."},{"key":"321_CR20","unstructured":"Hwang, F.W., Richards, D.S., Winter, P.: The Steiner Tree Problem, vol.\u00a053 of Annals of Discrete Mathematics, North Holland (1992)"},{"key":"321_CR21","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Wagner, D. (eds): Drawing Graphs, Methods and Models, vol. 2025 of Lecture Notes in Computer Science. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44969-8"},{"key":"321_CR22","doi-asserted-by":"crossref","unstructured":"Lengauer, T.: VLSI theory. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 835\u2013868. Elsevier and MIT Press (1990)","DOI":"10.1016\/B978-0-444-88071-0.50021-7"},{"key":"321_CR23","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An O( $$\\sqrt{|V|} |{E}|$$ | V | | E | ) algorithm for finding maximum matching in general graphs. In: Proceedings of Foundations Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"321_CR24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-005-1187-5","volume":"45","author":"M Mucha","year":"2006","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via Gaussian elimination. Algorithmica 45, 3\u201320 (2006)","journal-title":"Algorithmica"},{"key":"321_CR25","doi-asserted-by":"crossref","unstructured":"Nishizeki, T., Rahman, Md.S.: Planar Graph Drawing. World Scientific, Singapore (2004)","DOI":"10.1142\/5648"},{"key":"321_CR26","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"JPC Petersen","year":"1891","unstructured":"Petersen, J.P.C.: Die theorie der regul\u00e4ren graphen. Acta Math. 15, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"321_CR27","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"321_CR28","doi-asserted-by":"crossref","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 representation of planar graphs. Discrete Comput. Geom. 1, 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"321_CR29","unstructured":"Thompson, C.D.: A Complexity Theory for VLSI. Ph.D. thesis, Carnegie-Mellon University (1980)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0321-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0321-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0321-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T18:26:55Z","timestamp":1569349615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0321-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,16]]},"references-count":29,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["321"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0321-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,16]]}}}