{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T05:34:45Z","timestamp":1771911285321,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,3,1]],"date-time":"1995-03-01T00:00:00Z","timestamp":794016000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,3]]},"DOI":"10.1007\/bf01277954","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T06:00:40Z","timestamp":1111644040000},"page":"24-42","source":"Crossref","is-referenced-by-count":8,"title":["On the complexity of planar Boolean circuits"],"prefix":"10.1007","volume":"5","author":[{"given":"Gy\ufffdrgy","family":"Tur\ufffdn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon andW. Maass, Meanders and their application in lower bounds arguments.J. Comput. System Sci. 37 (1988), 118?129.","journal-title":"J. Comput. System Sci."},{"key":"CR2","first-page":"73","volume":"6","author":"A. E. Andreev","year":"1986","unstructured":"A. E. Andreev, On a method giving larger than quadratic effective lower bounds for the complexity of ?-schemes.Vestnik Moscow Univ. Ser. 1 (Math. Mech.) 6, 1986, 73?76. (In Russian.)","journal-title":"Vestnik Moscow Univ. Ser. 1 (Math. Mech.)"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, andM. Szegedy, Multiparty protocols, pseudorandom generators for Logspace and time-space trade-offs.J. Comput. System Sci. 45 (1992), 204?232.","journal-title":"J. Comput. System Sci."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","volume":"74","author":"L. Babai","year":"1990","unstructured":"L. Babai, P. Pudl\u00e1k, V. R\u00f6dl, andE. Szemer\u00e9di, Lower bounds to the complexity of symmetric Boolean functions.Theoret. Comput. Sci. 74 (1990), 313?323.","journal-title":"Theoret. Comput. Sci."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S. N. Bhatt","year":"1984","unstructured":"S. N. Bhatt andF. T. Leighton, A framework for solving VLSI graph layout problems.J. Comput. System Sci. 28(1984), 300?343.","journal-title":"J. Comput. System Sci."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber, Z. Galil, Explicit construction of linear size superconcentrators.J. Comput. System Sci. 22 (1981), 407?420.","journal-title":"J. Comput. System Sci."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"H. D. Gr\u00f6ger, A new partition lemma for planar graphs and its application to circuit complexity. InProceedings FCT 1991, ed.L. Budach,Lecture Notes in Computer Science 529, Springer-Verlag, 1991, 220?229.","DOI":"10.1007\/3-540-54458-5_66"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(87)90194-3","volume":"24","author":"P. Hochschild","year":"1987","unstructured":"P. Hochschild, Multiple cuts, input repetition, and VLSI complexity.Inform. Process. Lett. 24 (1987), 19?24.","journal-title":"Inform. Process. Lett."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, Optimal allocation of computational resources in VLSI. InProc. 23rd Ann. IEEE Symp. Found. Comput. Sci., 1982, 379?385.","DOI":"10.1109\/SFCS.1982.32"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/978-3-642-68402-9_7","volume-title":"VLSI Systems and Computations","author":"Z. M. Kedem","year":"1981","unstructured":"Z. M. Kedem andA. Zorat, Replication of inputs may save computational resources in VLSI. InVLSI Systems and Computations, ed.H. T. Kung, R. Sproull, andG. Steele. Comput. Sci. Press, Rockwille MD, 1981, 52?60."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem and A. Zorat, On relations between input and communication\/computation in VLSI. InProc. 22nd Ann. IEEE Symp. Found. Comput. Sci., 1981, 37?41.","DOI":"10.1109\/SFCS.1981.26"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and R. Sedgewick, Lower bounds for VLSI. InProc. Thirteenth Ann. ACM Symp. Theor. Comput., 1981, 300?307.","DOI":"10.1145\/800076.802482"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton andR. E. Tarjan, A planar separator theorem.SIAM J. Appl. Math. 36 (1979), 177?189.","journal-title":"SIAM J. Appl. Math."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton andR. E. Tarjan, Applications of a planar separator theorem.SIAM J. Comput. 9 (1980), 615?626.","journal-title":"SIAM J. Comput."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"W. Maass, G. Schnitger, and E. Szemer\u00e9di, Two tapes are better than one for off-line Turing machines. InProc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 94?100.","DOI":"10.1145\/28395.28406"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BF01275490","volume":"3","author":"W. Maass","year":"1993","unstructured":"W. Maass, G. Schnitger, E. Szemer\u00e9di, G. Tur\u00e1n, Two tapes versus one for off-line Turing machines.Comput complexity 3 (1993), 392?401.","journal-title":"Comput complexity"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/TC.1981.1675758","volume":"30","author":"W. F. McColl","year":"1981","unstructured":"W. F. McColl, Planar crossovers.IEEE Trans. Comput. 30 (1981), 223?225.","journal-title":"IEEE Trans. Comput."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"W. F. McColl, On the planar monotone computation of threshold functions. InProc. 2nd Symp. Theoret. Aspects of Comput. Sci., ed.K. Mehlhorn,Lecture Notes in Computer Science 182, Springer-Verlag, 1985, 219?230.","DOI":"10.1007\/BFb0024011"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"W. F. McColl, Planar circuits have short specifications. InProc. 2nd Symp. Theoret. Aspects of Comput. Sci., ed.K. Mehlhorn,Lecture Notes in Computer Science 182, Springer-Verlag, 1985, 231?242.","DOI":"10.1007\/BFb0024012"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(87)90180-3","volume":"24","author":"W. F. McColl","year":"1987","unstructured":"W. F. McColl, M. S. Paterson, The planar realization of Boolean functions.Inform. Process. Lett. 24 (1987), 165?170.","journal-title":"Inform. Process. Lett."},{"key":"CR21","first-page":"765","volume":"169","author":"E. J. Nechiporuk","year":"1966","unstructured":"E. J. Nechiporuk, A Boolean function.Dokl. Akad. Nauk SSSR 169 (1966), 765?766.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"W. J. Paul","year":"1977","unstructured":"W. J. Paul, A 2.5n lower bound on the combinational complexity of Boolean functions.SIAM J. Comput. 6 (1977), 427?443.","journal-title":"SIAM J. Comput."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-642-68402-9_8","volume-title":"VLSI Systems and Computations","author":"J. E. Savage","year":"1981","unstructured":"J. E. Savage, Planar circuit complexity and the performance of VLSI algorithms. InVLSI Systems and Computations, ed.H. T. Kung, R. Sproull, andG. Steele. Comput. Sci. Press Rockwille MD, 1981, 61?67. Also in INRIA Report77 (1981)."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0022-0000(84)90033-3","volume":"29","author":"J. E. Savage","year":"1984","unstructured":"J. E. Savage, The performance of multilective VLSI algorithms.J. Comput. System Sci. 29 (1984), 243?272.","journal-title":"J. Comput. System Sci."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(89)90172-5","volume":"30","author":"G. Tur\u00e1n","year":"1989","unstructured":"G. Tur\u00e1n, Lower bounds for synchronous circuits and planar circuits.Inform. Process. Lett. 30 (1989), 37?40.","journal-title":"Inform. Process. Lett."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"G. Tur\u00e1n, On restricted Boolean circuits. InProceedings FCT 1989, ed.J. Csirik, J. Demetrovics, and F. G\u00e9cseg,Lecture Notes in Computer Science 380, Springer-Verlag, 1989, 460?469.","DOI":"10.1007\/3-540-51498-8_45"},{"key":"CR27","volume-title":"Computational Aspects of VLSI","author":"J. D. Ullman","year":"1984","unstructured":"J. D. Ullman,Computational Aspects of VLSI. Comput. Sci. Press, Rockwille MD, 1984."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1109\/TC.1983.1676221","volume":"32","author":"J. Vuillemin","year":"1983","unstructured":"J. Vuillemin, A combinatorial limit to the computing power of VLSI circuits.IEEE Trans. Comput. 32 (1983), 294?300.","journal-title":"IEEE Trans. Comput."},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"I. Wegener, The Complexity of Boolean Functions.Wiley-Teubner Series in Comput. Sci., 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01277954.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01277954\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01277954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:58:25Z","timestamp":1586177905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01277954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["BF01277954"],"URL":"https:\/\/doi.org\/10.1007\/bf01277954","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}