{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T21:44:02Z","timestamp":1774820642571,"version":"3.50.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":30,"publisher":"Springer-Verlag","isbn-type":[{"value":"354050110X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0017151","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T06:30:09Z","timestamp":1132727409000},"page":"280-290","source":"Crossref","is-referenced-by-count":5,"title":["Edge separators for planar graphs and their applications"],"prefix":"10.1007","author":[{"given":"Krzystof","family":"Diks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hristo N.","family":"Djidjev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ondrej","family":"Sykora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imrich","family":"Vrto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0743-7315(87)90018-9","volume":"4","author":"F. Berman","year":"1987","unstructured":"F. Berman, L. Snyder, On mapping parallel algorithms into parallel architectures, J. of Parallel and Distributed Computing, Vol.4, 1987, pp. 439\u2013458.","journal-title":"J. of Parallel and Distributed Computing"},{"issue":"2","key":"25_CR2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1137\/0603022","volume":"3","author":"H.N. Djidjev","year":"1982","unstructured":"H.N. Djidjev, On the problem of partitioning planar graphs, SIAM J. Alg. Disc. Meth., Vol. 3, No. 2, 1982, pp.229\u2013240.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"25_CR3","first-page":"369","volume":"11","author":"H.N. Djidjev","year":"1985","unstructured":"H.N. Djidjev, A Linear algorithm for partitioning graphs of fixed genus, SERDICA, Vol. 11, 1985, 369\u2013387.","journal-title":"SERDICA"},{"key":"25_CR4","first-page":"319","volume":"11","author":"H.N. Djidjev","year":"1985","unstructured":"H.N. Djidjev, A separator theorem for graphs of fixed genus, SERDICA, Vol. 11, 1985, pp. 319\u2013329.","journal-title":"SERDICA"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/359361.359447","volume":"21","author":"R.A. Millo De","year":"1978","unstructured":"R.A. De Millo, S.C. Eisenstat, R.J.L. Lipton, Preserving average proximity in arrays, Comm. ACM, 21, 1978, pp. 228\u2013230.","journal-title":"Comm. ACM"},{"key":"25_CR6","unstructured":"H.Gazit, An improved algorithm for separating planar graphs, manuscript."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"J.R.Gilbert, J.P.Hutchinson, R.E.Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithsm, No.5, 1984, pp. 391\u2013398.","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"25_CR8","unstructured":"J.R.Gilbert, Graph separator theorem and sparse Gaussian elimination, Ph.D. thesis, Stanford University, 1980."},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"H.Gazit, G.L.Miller, A parallel algorithm for finding a separator for planar graphs. In: Proc. 28-th. Foundations of Computer Science, IEEE, 1987, 238\u2013248.","DOI":"10.1109\/SFCS.1987.3"},{"issue":"2","key":"25_CR10","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1137\/0608018","volume":"8","author":"L.S. Heath","year":"1987","unstructured":"L.S. Heath, Embedding outerplanar graphs in small books, SIAM J. Alg. Disc. Meth., Vol.8, No.2, 1987, pp. 198\u2013218.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"2","key":"25_CR11","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/0211018","volume":"11","author":"J. Hong","year":"1982","unstructured":"J. Hong, A.L. Rosenberg, Graphs that are almost binary trees, SIAM J. Comput., Vol. 11, No. 2, 1982, pp. 227\u2013242.","journal-title":"SIAM J. Comput."},{"key":"25_CR12","first-page":"109","volume":"31","author":"M.A. Jordanskij","year":"1976","unstructured":"M.A. Jordanskij, Minimal numberings of tree vertices, Probl. Kib., Vol. 31, 1976, pp.109\u2013133 (in Russian).","journal-title":"Probl. Kib."},{"key":"25_CR13","first-page":"259","volume-title":"Proc. 24-th Ann. Symp. on Theory of Computing","author":"D.B. Johnson","year":"1983","unstructured":"D.B. Johnson, S.M. Venkatesan, Partition of planar flows in networks. In: Proc. 24-th Ann. Symp. on Theory of Computing, ACM, New York, 1983, pp. 259\u2013263."},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton, D.J. Rose, R.E. Tarjan, Generalized nested dissection, SIAM J. Numer. Anal., 16, 1979, 346\u2013358.","journal-title":"SIAM J. Numer. Anal."},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"C.E.Leiserson, Area efficient graph layout (for VLSI), In: Proc. 21-st Foundations of Computer Science, IEEE, Syracuse, 1980, pp. 270\u2013281.","DOI":"10.1109\/SFCS.1980.13"},{"key":"25_CR16","first-page":"85","volume-title":"Proc. 23-rd Foundations of Computer Science","author":"F.T. Leighton","year":"1982","unstructured":"F.T. Leighton, A layout strategy which is provably good, In: Proc. 23-rd Foundations of Computer Science, IEEE, San Francisco, 1982, pp. 85\u201398."},{"issue":"2","key":"25_CR17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., Vol. 36, No. 2, 1979, pp. 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"25_CR18","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"R.J. Lipton, R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Computing, Vol. 9, No.3, 1980, pp. 615\u2013627.","journal-title":"SIAM J. Computing"},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"G.L. Miller, Finding small simple cycle-separators for 2-connected planar graphs, J. of Comp. and System Science, Vol. 32, 1986, pp. 265\u2013279.","journal-title":"J. of Comp. and System Science"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"B.Monien, The complexity of embedding graphs into binary trees, In: FCTo 85, LNCS 199, pp. 300\u2013309.","DOI":"10.1007\/BFb0028814"},{"issue":"5","key":"25_CR21","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"M. S","year":"1979","unstructured":"S. Mitchel, Linear algorithm to recognize outerplanar and maximal outerplanar graphs, IPL, Vol. 9, No.5, 1979, pp.229\u2013232.","journal-title":"IPL"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"S.Rao, Finding near optimal separators in planar graphs, In: Proc. 28-th Foundations of Computer Science. IEEE, 1987, pp. 225\u2013237.","DOI":"10.1109\/SFCS.1987.26"},{"issue":"6","key":"25_CR23","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(87)90206-7","volume":"25","author":"S.S. Ravi","year":"1987","unstructured":"S.S. Ravi, H.B. Hunt, An application of the planar separator theorem to counting problem, IPL, Vol. 25, No.6, 1987, pp.317\u2013322.","journal-title":"IPL"},{"key":"25_CR24","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/0196-6774(86)90029-5","volume":"7","author":"D. Richards","year":"1986","unstructured":"D. Richards, Finding short cycles in planar graphs using separators, J. of Algorithms, Vol. 7, 1986, pp. 382\u2013394.","journal-title":"J. of Algorithms"},{"issue":"6","key":"25_CR25","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1109\/TC.1985.5009416","volume":"C-34","author":"A.L. Rosenberg","year":"1985","unstructured":"A.L. Rosenberg, A hypergraph model for fault-tolerant VLSI processor arrays, IEEE Trans. on Computers, C-34, No. 6, 1985, pp. 578\u2013584.","journal-title":"IEEE Trans. on Computers"},{"key":"25_CR26","first-page":"63","volume":"29","author":"M.A. Scheidwasser","year":"1974","unstructured":"M.A. Scheidwasser, On the length and the width of embeddings of graphs in meshes, Probl. Kib., Vol. 29, 1974, pp.63\u2013102 (in Russian).","journal-title":"Probl. Kib."},{"issue":"2","key":"25_CR27","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"C-30","author":"J.G. Valiant","year":"1981","unstructured":"J.G. Valiant, Universality consideration in VLSI circuits, IEEE Trans. on Computers, C-30, No.2, 1981, pp. 135\u2013140.","journal-title":"IEEE Trans. on Computers"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"S.M.Venkatesan, Improved constants for some separator theorems, J. of Algorithms, to appear.","DOI":"10.1016\/0196-6774(87)90051-4"},{"key":"25_CR29","unstructured":"S.M.Venkatesan, On separating a planar graph into two halves, Submitted to SIAM J. of Discrete Mathematics."},{"key":"25_CR30","series-title":"Lecture Notes in Computer Science","volume-title":"Linear and book embeddings of graphs","author":"M. Yannakakis","year":"1986","unstructured":"M. Yannakakis, Linear and book embeddings of graphs, in: Proc. Aegean Workshop on Computing, July 8\u201311, 1986, Lecture Notes in Computer Science, Vol. 227, Springer-Verlag, Berlin, 1986."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1988"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0017151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:26:27Z","timestamp":1586579187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354050110X"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/bfb0017151","relation":{},"subject":[]}}