{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T19:35:25Z","timestamp":1694633725835},"reference-count":137,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1999,9,1]],"date-time":"1999-09-01T00:00:00Z","timestamp":936144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. & Technol."],"published-print":{"date-parts":[[1999,9]]},"DOI":"10.1007\/bf02948786","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T23:52:03Z","timestamp":1221263523000},"page":"447-459","source":"Crossref","is-referenced-by-count":0,"title":["Orthogonal drawings of graphs for the automation of VLSI circuit design"],"prefix":"10.1007","volume":"14","author":[{"given":"Yanpei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02948786_CR1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K Kuratowski","year":"1930","unstructured":"Kuratowski K. Sur le Problem des Coubes Gauches en Topologie.Fund. Math., 1930, 15: 271\u2013283.","journal-title":"Fund. Math."},{"key":"BF02948786_CR2","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1215\/S0012-7094-37-00336-3","volume":"3","author":"S MacLane","year":"1937","unstructured":"MacLane S. A structural characterization of planar combinatorial graphs.Duke Math. J., 1937, 3: 460\u2013472.","journal-title":"Duke Math. J."},{"key":"BF02948786_CR3","doi-asserted-by":"crossref","first-page":"22","DOI":"10.4064\/fm-28-1-22-32","volume":"28","author":"S MacLane","year":"1937","unstructured":"MacLane S. A combinatorial condition for planar graphs.Fund. Math., 1937, 28: 22\u201332.","journal-title":"Fund. Math."},{"key":"BF02948786_CR4","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney H. Non-separable and planar graph.Trans. AMS, 1932, 34: 339\u2013162.","journal-title":"Trans. AMS"},{"key":"BF02948786_CR5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.4064\/fm-21-1-73-84","volume":"21","author":"H Whitney","year":"1933","unstructured":"Whitney H. Planar graphs.Fund. Math., 1933, 21: 73\u201384.","journal-title":"Fund. Math."},{"key":"BF02948786_CR6","first-page":"276","volume":"4","author":"H Whitney","year":"1937","unstructured":"Whitney H. On regular closed curves in the plane.Compositio Math., 1937, 4: 276\u2013284.","journal-title":"Compositio Math."},{"key":"BF02948786_CR7","first-page":"505","volume":"5","author":"W T Wu","year":"1955","unstructured":"Wu W T. The realization of complexies in the Euclidean space.Acta Math. Sinica, 1955, 5: 505\u2013452 (in Chinese),","journal-title":"Acta Math. Sinica"},{"key":"BF02948786_CR8","volume-title":"A theory of Imbedding, Immersion, and Isotopy of Polytopes in an Euclidean Space","author":"W T Wu","year":"1965","unstructured":"Wu W T. A theory of Imbedding, Immersion, and Isotopy of Polytopes in an Euclidean Space. Science Press, Beijing, 1965."},{"issue":"2","key":"BF02948786_CR9","first-page":"226","volume":"19","author":"W T Wu","year":"1974","unstructured":"Wu W T. Planar embedding of linear graphs.Sci. Bull. (KEXUETONGBAO), 1974, 19(2): 226\u2013228 (in Chinese).","journal-title":"Sci. Bull. (KEXUETONGBAO)"},{"key":"BF02948786_CR10","series-title":"Lect. Notes in Math.","volume-title":"Rational Homotopy Type","author":"W T Wu","year":"1987","unstructured":"Wu W T. Rational Homotopy Type. Lect. Notes in Math. 1246, Springer, New York\/Heidelberg\/Berlin, 1987."},{"key":"BF02948786_CR11","first-page":"20","volume":"1","author":"W T Wu","year":"1973","unstructured":"Wu W T. Mathematical problems in the design of integrated circuits.Math. Theory Practice, 1973, 1: 20\u201340 (in Chinese).","journal-title":"Math. Theory Practice"},{"key":"BF02948786_CR12","first-page":"290","volume":"5","author":"W T Wu","year":"1985","unstructured":"Wu W T. On the planar embedding of linear graphs I.J. Syst. Sci. Math, 1985, 5: 290\u2013320.","journal-title":"J. Syst. Sci. Math"},{"key":"BF02948786_CR13","first-page":"23","volume":"6","author":"W T Wu","year":"1986","unstructured":"Wu W T. On the planar embedding of linear graphs II.J. Syst. Sci. Math., 1986, 6: 23\u201335.","journal-title":"J. Syst. Sci. Math."},{"key":"BF02948786_CR14","volume-title":"The Realization of Polytopes in the Euclidean Space","author":"W T Wu","year":"1978","unstructured":"Wu W T. The Realization of Polytopes in the Euclidean Space. Science Press, Beijing, 1978 (in Chinese)."},{"key":"BF02948786_CR15","volume-title":"Selected Papers of Wu Wenjun","author":"W T Wu","year":"1986","unstructured":"Wu W T. Selected Papers of Wu Wenjun. Shandong Education Press, Jinan, 1986 (in Chinese)."},{"key":"BF02948786_CR16","volume-title":"On Mathematical Mechanization on by Wu Wenjun","author":"W T Wu","year":"1995","unstructured":"Wu W T. On Mathematical Mechanization on by Wu Wenjun. Shandong Education Press, Jinan, 1995 (in Chinese)."},{"key":"BF02948786_CR17","volume-title":"Embeddability Theory of Graphs","author":"Y P Liu","year":"1994","unstructured":"Liu Y P. Embeddability Theory of Graphs. Science Press, Beijing, 1994, (in Chinese)."},{"key":"BF02948786_CR18","volume-title":"Embeddability in Graphs","author":"Y P Liu","year":"1995","unstructured":"Liu Y P. Embeddability in Graphs. Kluwer, Dordrecht\/Boston\/London, 1995."},{"key":"BF02948786_CR19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4153\/CJM-1956-004-9","volume":"8","author":"W T Tutte","year":"1956","unstructured":"Tutte W T. A class of Abelian groups.Canad. J. Math., 1956, 8: 13\u201328.","journal-title":"Canad. J. Math."},{"key":"BF02948786_CR20","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"W T Tutte","year":"1970","unstructured":"Tutte W T. Toward a theory of crossing numbers.J. Comb. Theory, 1970, 8: 45\u201353.","journal-title":"J. Comb. Theory"},{"key":"BF02948786_CR21","first-page":"395","volume":"1","author":"Y P Liu","year":"1978","unstructured":"Liu Y P. Module 2 programming and planar embedding.Acta Math. Appl Sinica, 1978, 1: 395\u2013406 (in Chinese).","journal-title":"Acta Math. Appl Sinica"},{"key":"BF02948786_CR22","unstructured":"Liu Y P. On the linearity of testing planarity of a graph. Comb. Optim. CORR84-4, University of Waterloo, 1984; Also inChinese Ann. Math., 1986, 7B: 425\u2013434."},{"key":"BF02948786_CR23","doi-asserted-by":"crossref","unstructured":"Liu Y P. A new approach to the linearity of testing planarity of graphs. Report, Rutgers University, 1984; Also inActa Math. Appl. Sinica, Eng. Series, 1988, 4: 257\u2013265.","DOI":"10.1007\/BF02006222"},{"key":"BF02948786_CR24","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0167-5060(08)70037-2","volume":"9","author":"P Rosenstiehl","year":"1980","unstructured":"Rosenstiehl P. Preuve algebrique du critere de planarite de Wu(Wenjun)-Liu(Yanpei).Ann. Discrete Math., 1980, 9: 67\u201378.","journal-title":"Ann. Discrete Math."},{"key":"BF02948786_CR25","doi-asserted-by":"crossref","unstructured":"Cook S A. The complexity of theorem proving procedures. InProc. 3rd ACM Symp. Comput., 1971, pp.151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF02948786_CR26","unstructured":"Garey M R, Johnson D S. Computer and Intractability-A Guide to the Theory of NP-Completeness, Freeman W H (eds.), San Francisco, 1979."},{"key":"BF02948786_CR27","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R J Lipton","year":"1979","unstructured":"Lipton R J, Tarjan R E. A separator theorem for planar graphs.SIAM J. Appl. Math., 1979, 36: 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02948786_CR28","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R J Lipton","year":"1980","unstructured":"Lipton R J, Tarjan R E. Applications of a planar separator theorem.SIAM J. Comput., 1980, 9: 615\u2013627.","journal-title":"SIAM J. Comput."},{"key":"BF02948786_CR29","volume-title":"Theory of Rectilinear Layouts","author":"Y P Liu","year":"1997","unstructured":"Liu Y P. Theory of Rectilinear Layouts. China Railway Publishing House, Beijing, 1997 (in Chinese)."},{"key":"BF02948786_CR30","doi-asserted-by":"crossref","unstructured":"Hopcroft J, Tarjan R. Isomorphism of planar graphs. InComplexity of Computer Computations, Miller Ret al. (eds.), Plenum, 1972, pp.131\u2013152.","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"BF02948786_CR31","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R. Dividing a graph into triconnected components.SIAM J. Comput., 1973, 2: 135\u2013158.","journal-title":"SIAM J. Comput."},{"key":"BF02948786_CR32","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft J, Tarjan R. Efficient planarity testing.J. ACM., 1974, 21: 549\u2013568.","journal-title":"J. ACM."},{"key":"BF02948786_CR33","first-page":"517","volume":"10","author":"L Auslander","year":"1961","unstructured":"Auslander L, Parter S V. On imbedding graphs in sphere.J. Math. Mech., 1961, 10: 517\u2013523.","journal-title":"J. Math. Mech."},{"key":"BF02948786_CR34","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1137\/0216061","volume":"16","author":"B Becker","year":"1987","unstructured":"Becker B, Hotz G. On the optimal layout of planar graphs with fixed boundary.SIAM J. Comput., 1987, 16: 946\u2013972.","journal-title":"SIAM J. Comput."},{"key":"BF02948786_CR35","first-page":"79","volume":"2","author":"Ja Dambit","year":"1966","unstructured":"Dambit Ja. Embedding of a graph into the plane.Latvian Math., 1966, Yearbook 2: 79\u201393.","journal-title":"Latvian Math."},{"key":"BF02948786_CR36","first-page":"33","volume":"8","author":"G Demoucron","year":"1964","unstructured":"Demoucron G, Malgrange Y, Pertuiset R. Graphe planaires, reconnaissance et construction de representations planaires topologiques.Rev. Francaise Recherche Operationnelle, 1964, 8: 33\u201347.","journal-title":"Rev. Francaise Recherche Operationnelle"},{"key":"BF02948786_CR37","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/321921.321929","volume":"33","author":"N Deo","year":"1976","unstructured":"Deo N. Note on Hopcroft and Tarjan\u2019s planarity algorithm.J. ACM, 1976, 33: 74\u201375.","journal-title":"J. ACM"},{"key":"BF02948786_CR38","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1109\/TCT.1970.1083103","volume":"17","author":"W L Engle","year":"1970","unstructured":"Engle W L. An algorithm for embedding graphs in the plane with certain constraints.IEEE Trans. Cir. Theory, 1970, CT-17: 250\u2013252.","journal-title":"IEEE Trans. Cir. Theory"},{"issue":"2","key":"BF02948786_CR39","first-page":"254","volume":"23","author":"G J Fisher","year":"1996","unstructured":"Fisher G J, Wing O. Computer recognition and extraction of planar graphs from the incidence matrix.IEEE Trans. Cir. Theory, 1996 CT-23(2): 254\u2013263.","journal-title":"IEEE Trans. Cir. Theory"},{"key":"BF02948786_CR40","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/j.1538-7305.1973.tb03188.x","volume":"52","author":"A J Goldstein","year":"1973","unstructured":"Goldstein A J, Schweikert D G. A proper model for testing the planarity of electrical circuits.Bell Syst. Tech. J., 1973, 52: 135\u2013142.","journal-title":"Bell Syst. Tech. J."},{"key":"BF02948786_CR41","unstructured":"Hopcroft J. Ann logn algorithm for isomorphism of planar triply connected graphs. InTheory of Machines and Computation, Kohavi Zet al., (eds.), Acad. Press, 1971, pp.189\u2013196."},{"key":"BF02948786_CR42","unstructured":"Hopcroft J, Tarjan R. Planarity testing inV logV steps: Extended abstract. InProc. IFIP Cong., 1971, pp.85\u201390."},{"key":"BF02948786_CR43","first-page":"82","volume":"1","author":"A K Hope","year":"1971","unstructured":"Hope A K. A planar graph drawing program.Solfware-Practice and Experience, 1971, 1: 82\u201391.","journal-title":"Solfware-Practice and Experience"},{"key":"BF02948786_CR44","doi-asserted-by":"crossref","unstructured":"Hotz G. The embedding of graphs in the 2-sphere.Z. Angew. Math. Mech., 1965, 45.","DOI":"10.1002\/zamm.19650459020"},{"key":"BF02948786_CR45","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/BF01361186","volume":"167","author":"G Hotz","year":"1966","unstructured":"Hotz G. Embedding of graphs in the plane.Math. Ann., 1966 167: 214\u2013223.","journal-title":"Math. Ann."},{"key":"BF02948786_CR46","doi-asserted-by":"crossref","unstructured":"Inukai T, Weinberg L. Planar, coplanar, and totally planarn-port networks.IEEE Trans. Cir. Syst., 1976, Case-23.","DOI":"10.1109\/TCS.1976.1084193"},{"issue":"3","key":"BF02948786_CR47","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/31.1746","volume":"35","author":"R Jayakumar","year":"1988","unstructured":"Jayakumar R, Thulasiraman K, Swamy M N S. Planar embeddings: Linear time algorithms for vertex placement and edge ordering.IEEE Trans. Cir. Syst., 1988 35 (3): 334\u2013344.","journal-title":"IEEE Trans. Cir. Syst."},{"key":"BF02948786_CR48","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D G Kirkpatrick","year":"1983","unstructured":"Kirkpatrick D G. Optimal search in planar subdivision.SIAM J. Comput., 1983, 12: 28\u201335.","journal-title":"SIAM J. Comput."},{"key":"BF02948786_CR49","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02242387","volume":"10","author":"B Knauer","year":"1972","unstructured":"Knauer B. Normalformen planar graphen I.Computing, 1972, 10: 121\u2013136.","journal-title":"Computing"},{"key":"BF02948786_CR50","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02242388","volume":"10","author":"B Knauer","year":"1972","unstructured":"Knauer B. Normalformen planar graphen II.Computing, 1972, 10: 137\u2013152.","journal-title":"Computing"},{"key":"BF02948786_CR51","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1145\/321879.321885","volume":"22","author":"B Knauer","year":"1975","unstructured":"Knauer B. A simple planarity criterion.J. ACM, 1975, 22: 226\u2013230.","journal-title":"J. ACM"},{"key":"BF02948786_CR52","doi-asserted-by":"crossref","unstructured":"Lefschetz S. Planar graphs and related topics. InProc. Nat. Acad. Sci. 1965, 54: 1763\u20131765.","DOI":"10.1073\/pnas.54.6.1763"},{"key":"BF02948786_CR53","unstructured":"Lempel A, Even S, Cederbaum I. An algorithm for planarity testing of graphs. In Graph Theory Rosenstiehl P (ed.), InProc. Int. Symp., Rome, 1967, p.215."},{"key":"BF02948786_CR54","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T Lenganer","year":"1989","unstructured":"Lenganer T. Hierarchical planarity testing algorithms.J. ACM., 1989, 36: 474\u2013509.","journal-title":"J. ACM."},{"key":"BF02948786_CR55","first-page":"45","volume":"6","author":"G S Plesnevic","year":"1963","unstructured":"Plesnevic G S. Embedding a graph in the plane.Vycislitellnyes Sistemy, 1963, 6: 45\u201353.","journal-title":"Vycislitellnyes Sistemy"},{"key":"BF02948786_CR56","first-page":"521","volume":"15","author":"P Rosenstiehl","year":"1976","unstructured":"Rosenstiehl P. Caracterisation des graphes planaires par une diagonale absreacte.Cong. Numer., 1976, 15: 521\u2013527.","journal-title":"Cong. Numer."},{"key":"BF02948786_CR57","unstructured":"Rubin F. An algorithm for testing the planarity of a graph.IEEE Computer Group Respositery, R74-73, 1974."},{"key":"BF02948786_CR58","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/T-C.1975.224179","volume":"24","author":"F Rubin","year":"1975","unstructured":"Rubin F. An improved algorithm for testing the planarity of a graph.IEEE Trans. on Computers, 1975, C-24: 113\u2013121.","journal-title":"IEEE Trans. on Computers"},{"key":"BF02948786_CR59","doi-asserted-by":"crossref","unstructured":"Tutte W T. How to draw a graph. InProc. London Math. Soc., 1963, 13(Ser.3): 743\u2013768.","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"BF02948786_CR60","unstructured":"Ulrich J W. A computational theory of planar embedding. InPh. D. Thesis, Univ. Texas, Austin, 1968."},{"key":"BF02948786_CR61","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0118030","volume":"18","author":"J W Ulrich","year":"1970","unstructured":"Ulrich J W. A characterization of planar oriented graphs.SIAM J. Appl. Math., 1970, 18: 364\u2013371.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02948786_CR62","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1112\/jlms\/s1-26.4.256","volume":"26","author":"P Unger","year":"1951","unstructured":"Unger P. A theorem on planar graph, components, and subgraphs.J. London Math. Soc., 1951, 26: 256\u2013262.","journal-title":"J. London Math. Soc."},{"key":"BF02948786_CR63","unstructured":"Weinberg L. Two new characterization of planar graphs. InProc. 5-th Allerton Conf. Cir. Syst., Uni. Ill., 1967."},{"key":"BF02948786_CR64","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0167-5060(08)70719-2","volume":"6","author":"S G Williamson","year":"1980","unstructured":"Williamson S G. Embedding graphs in the plane-Algorithm aspects.Am. Discrete Math., 1980, 6: 349\u2013384.","journal-title":"Am. Discrete Math."},{"key":"BF02948786_CR65","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1109\/TCT.1966.1082522","volume":"13","author":"O Wing","year":"1966","unstructured":"Wing O. On drawing a planar graph.IEEE Trans. Cir. Theory 1966, 13: 112\u2013114.","journal-title":"IEEE Trans. Cir. Theory"},{"key":"BF02948786_CR66","doi-asserted-by":"crossref","unstructured":"Liu Y P, Marchioro P, Petreschi R. At most single-bend embeddings of cubic graphs. Research Report SI-92\/01. Dept. Computer Science, Uni. \u00abLa Sapienza\u201d of Rome, 1992. Also inApplied Math. (A J. Chinese Unis.), 1994, B9: 127\u2013142.","DOI":"10.1007\/BF02662066"},{"key":"BF02948786_CR67","doi-asserted-by":"crossref","unstructured":"Liu Y P, Marchioro P, Petreschi R, Simeone B. Theoretical results on at most 1-bend embeddability of graphs. Research Report Series A No.3, Department of Statistics, University of Rome \u201cLa Sapienza\u201d, 1990; Also inActa Math. Appl. Sinica, Eng., 1992, Series 8: 188\u2013192.","DOI":"10.1007\/BF02006154"},{"key":"BF02948786_CR68","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1360\/csb1991-36-14-1054","volume":"36","author":"Y P Liu","year":"1991","unstructured":"Liu Y P, Marchioro P, Petreschi R, Simeone B. On theoretical results of at most 1-embeddability of graphs.Chinese Science Bulletin, 1991, 36: 1054\u20131055.","journal-title":"Chinese Science Bulletin"},{"key":"BF02948786_CR69","unstructured":"Liu Y P, Morgana A. Simeone B. On the general theoretical results for rectilinear embeddability of graphs.KEXUE TONGBAO, (Chinese Ed.) 1990, 35: 1513\u20131514. Or seeChinese Science Bulletin (English Ed.), 1991, 36: 1490."},{"key":"BF02948786_CR70","doi-asserted-by":"crossref","unstructured":"Liu Y P, Morgana A, Simeone B. General theoretical results on rectilinear embeddability of graphs, Research Report Series A, No. 2, Department of Statistics, University of Rome \u00abLa Sapienza\u00bb, 1990; AlsoinActa Math. Appl. Sinica, Eng., 1991, Series 7: 187\u2013192.","DOI":"10.1007\/BF02006104"},{"key":"BF02948786_CR71","doi-asserted-by":"crossref","unstructured":"Liu Y P, Morgana A, Simeone B. A linear time algorithm for 3-bend embeddings of planar graphs in the grid. Research Report, Ser.A, No.1, Dept. Statistics, Uni. \u00abLa Sapienza\u00bb, Rome, 1993. Also inDiscrete Appl. Math., 1998, 81: 69\u201392.","DOI":"10.1016\/S0166-218X(97)00076-0"},{"key":"BF02948786_CR72","doi-asserted-by":"crossref","unstructured":"Liu Y P, Morgana A, Simeone B. A graph partition problem. Research Report, No.27, Inst. Appl. Math., Acad. Sinica, 1992. Also inActa Math. Appl. Sinica, Eng., 1996, Series 12: 393\u2013400.","DOI":"10.1007\/BF02029067"},{"key":"BF02948786_CR73","unstructured":"Liu Y P, Morgana A, Simeone B. Another linear time algorithm for finding 3-embeddings of a graph. Research Report, No.1, Inst. Appl. Math., Acad. Sinica, 1994."},{"key":"BF02948786_CR74","unstructured":"Liu Y P, Morgana A, Simeone B. Characterizations of a kind of orientations of a graph. Research Report, No.2, Inst. Appl. Math., Acad. Sinica, 1994."},{"key":"BF02948786_CR75","first-page":"413","volume":"8","author":"Y P Liu","year":"1994","unstructured":"Liu Y P. On the net-embeddability of graphs.Acta Math. Sinica, 1994, New Series, 8: 413\u2013423.","journal-title":"Acta Math. Sinica"},{"key":"BF02948786_CR76","first-page":"533","volume":"38","author":"Y P Liu","year":"1993","unstructured":"Liu Y P. On the efficient recognition on the net-extensibility of graphs.Chinese Science Bulletin, 1993, 38: 533\u2013536.","journal-title":"Chinese Science Bulletin"},{"key":"BF02948786_CR77","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/BF02662005","volume":"8","author":"Y P Liu","year":"1993","unstructured":"Liu Y P. Combinatorial optimization arising from VLSI circuit design.Applied Math., (JCU), 1993, B8: 218\u2013235.","journal-title":"Applied Math., (JCU)"},{"key":"BF02948786_CR78","first-page":"75","volume":"13","author":"H Fraysseix","year":"1982","unstructured":"Fraysseix H, Rosentiehl P. A depth \u2014 first search characterization of planarity.Ann. Discrete Math., 1982, 13: 75\u201380.","journal-title":"Ann. Discrete Math."},{"key":"BF02948786_CR79","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02579375","volume":"5","author":"H Fraysseix","year":"1985","unstructured":"Fraysseix H, Rosenstiehl P. A characterization of planar graphs by Tremaux order.Combinatorica, 1985, 5: 127\u2013155.","journal-title":"Combinatorica"},{"key":"BF02948786_CR80","first-page":"350","volume":"2","author":"Y P Liu","year":"1979","unstructured":"Liu Y P. Planarity testing nd planar embeddings of graphs.Acta Math. Appl. Sinica, 1979, 2: 350\u2013365 (in Chinese).","journal-title":"Acta Math. Appl. Sinica"},{"key":"BF02948786_CR81","doi-asserted-by":"crossref","unstructured":"Liu Y P. Boolean planarity characterization of graphs. RUTCOR Research Report RRR38-87, Rutgers University, 1987; Also inActa Math Sinica, 1988, New Series, 4: 316\u2013329.","DOI":"10.1007\/BF02560635"},{"key":"BF02948786_CR82","doi-asserted-by":"crossref","unstructured":"Liu Y P. Boolean approach to planar embeddings of a graph. RUTCOR Research Report RRR39-87, Rutgers University, 1987; Also inActa Math. Sinica, 1989, New Series, 5: 64\u201379.","DOI":"10.1007\/BF02107624"},{"key":"BF02948786_CR83","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF02216821","volume":"24","author":"Y P Liu","year":"1990","unstructured":"Liu Y P. Boolean characterizations of planarity and planar embeddings of graphs.Ann. Operations Research, 1990, 24: 165\u2013174.","journal-title":"Ann. Operations Research"},{"issue":"1","key":"BF02948786_CR84","first-page":"33","volume":"12","author":"X R Sun","year":"1989","unstructured":"Sun X R. On the complexity of testing the planarity by Wu(Wenjun)-Liu (Yanpei) Theorem, (in Chinese with English abstract). Chinese J. Comput., 1989, 12(1): 33\u201337.","journal-title":"Chinese J. Comput."},{"key":"BF02948786_CR85","unstructured":"Sun X R. Wu (Wenjun)-Liu (Yanpei) Theorem and planarity testing of graphs.Thesis, Inst. Applied Math., Acad. Sinica, 1987 (in Chinese)."},{"key":"BF02948786_CR86","doi-asserted-by":"crossref","unstructured":"Xu W X. An efficient algorithm for planarity testing based on Wu (Wenjun)-Liu (Yanpei)\u2019s criterion. InProc. 1-st China-USA Conf. Graph Theory and its Applications, Ann. N. Y. Acad. Sci., 1989, 576: 641\u2013652.","DOI":"10.1111\/j.1749-6632.1989.tb16445.x"},{"key":"BF02948786_CR87","doi-asserted-by":"crossref","unstructured":"Hopcroft J E, Wong J K. Linear time algorithm for isomorphism of planar graphs (extended abstract). In6-th Ann. ACM Symp. Comput., Seattle, 1974.","DOI":"10.1145\/800119.803896"},{"key":"BF02948786_CR88","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0020-0190(71)90019-6","volume":"1","author":"J Hopcroft","year":"1971","unstructured":"Hopcroft J, Tarjan R. A V2 algorithm for determining isomorphism of planar graphs.Inform. Process. Lett. 1971, 1: 32\u201334.","journal-title":"Inform. Process. Lett."},{"key":"BF02948786_CR89","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1109\/TCT.1966.1082573","volume":"13","author":"L Weinberg","year":"1966","unstructured":"Weinberg L. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs.IEEE Trans. Circuit Theory, 1966, CT-13: 142\u2013148.","journal-title":"IEEE Trans. Circuit Theory"},{"key":"BF02948786_CR90","unstructured":"Weinberg L. Plane representations and codes for planar graphs. InProc. 3-rd Ann. Allerton Conf. Cir. Syst., 1965, pp.733\u2013744."},{"key":"BF02948786_CR91","unstructured":"Weinberg L. Additional simple codes for planar graphs. InProc. 4-th Allerton Conf. Cir. Syst., 1966."},{"key":"BF02948786_CR92","unstructured":"Basden A, Nichols K G. New topological method for layout printed circuits. InProc. IEEE, 1973, 120(3): 325\u2013328."},{"key":"BF02948786_CR93","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0164-1212(84)90006-2","volume":"4","author":"C Batini","year":"1994","unstructured":"Batini C, Talamo M, Tamassia R. Computer aided layout of entity-relationship diagrams.IEEE J. Syst. Software, 1994, 4: 163\u2013173.","journal-title":"IEEE J. Syst. Software"},{"key":"BF02948786_CR94","doi-asserted-by":"crossref","unstructured":"Behzao M. A criterion for the planarity of the total graph of a graph. InProc. Cambridge Phil. Soc., 1967, 63: 679\u2013681.","DOI":"10.1017\/S0305004100041657"},{"key":"BF02948786_CR95","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S N Bhatt","year":"1984","unstructured":"Bhatt S N, Leighton F T. A framework for solving VLSI graph layout problems.J. Comput Syst. Scien., 1984, 28: 300\u2013343.","journal-title":"J. Comput Syst. Scien."},{"key":"BF02948786_CR96","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1109\/TCS.1983.1085357","volume":"30","author":"R W Chen","year":"1983","unstructured":"Chen R W, Kajitani Y, Chan S P. A graph- theoretic via minimization algorithm for two \u2014 layer printed circuit boards.IEEE Trans. Cir. Syst., 1983, Case-30: 284\u2013299.","journal-title":"IEEE Trans. Cir. Syst."},{"key":"BF02948786_CR97","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCT.1973.1083752","volume":"20","author":"L O Chua","year":"1973","unstructured":"Chua L O, Chen L K. On optimally sparse cycle and coboundary basis for a linear graph.IEEE Trans. Cir. Theory, 1973, CT-20: 495\u2013503.","journal-title":"IEEE Trans. Cir. Theory"},{"key":"BF02948786_CR98","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1109\/43.3222","volume":"7","author":"E M Charke","year":"1988","unstructured":"Charke E M, Feng Y. Escher-a geometrical layout system for recursively defined circuits.IEEE Trans. CAD, 1988, 7: 908\u2013918.","journal-title":"IEEE Trans. CAD"},{"issue":"12","key":"BF02948786_CR99","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1109\/TCS.1976.1084156","volume":"23","author":"W M Cleemput van","year":"1976","unstructured":"van Cleemput W M. Mathematical models for the circuit layout problem.IEEE Trans. Cir. Syst., 1976, Case-23(12): 759\u2013767.","journal-title":"IEEE Trans. Cir. Syst."},{"key":"BF02948786_CR100","unstructured":"van Cleemput W M, Linders J G. An improved graph theoretical model for the circuit layout problem. InProc. 11-th Design Automation Workshop, Denver, 1974."},{"key":"BF02948786_CR101","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1109\/43.3208","volume":"7","author":"J P Cohoon","year":"1988","unstructured":"Cohoon J P, Heck P L. BEAVER: a computational geometry based tool for switchbox routing.IEEE Trans. CAD, 1988, 7: 684\u2013697.","journal-title":"IEEE Trans. CAD"},{"key":"BF02948786_CR102","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1109\/43.7808","volume":"7","author":"J Cong","year":"1988","unstructured":"Cong J, Wong D F, Liu C L. A new approach to three or four layer channel routing.IEEE Trans. CAD, 1988, 7: 1094\u20131104.","journal-title":"IEEE Trans. CAD"},{"key":"BF02948786_CR103","first-page":"125","volume-title":"Handbook of OR Fundamentals","author":"D Z Du","year":"1995","unstructured":"Du D Z, Liu Y P. Combinatorial Optimization. Handbook of OR Fundamentals. Hui Get al. (eds.), Science Press, Beijing, 1995, pp.125\u2013167."},{"key":"BF02948786_CR104","unstructured":"Hu T C, Kuh S E. Theory and concepts of circuit layout. InVLSI Circuit Layout: Theory and Design. IEEE Press, 1985, pp.3\u201318."},{"key":"BF02948786_CR105","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9367-2","volume-title":"Applications of Algebraic Topology: Graphs and Networks","author":"S Lefschetz","year":"1975","unstructured":"Lefschetz S. Applications of Algebraic Topology: Graphs and Networks, Springer, New York\/Heidelberg\/ Berlin, 1975."},{"key":"BF02948786_CR106","volume-title":"Rectilinear Embeddings: Theory and Methods","author":"Y P Liu","year":"1994","unstructured":"Liu Y P. Rectilinear Embeddings: Theory and Methods. Beijing: Science Press, 1994 (in Chinese)."},{"key":"BF02948786_CR107","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/43.41502","volume":"8","author":"C S Rim","year":"1989","unstructured":"Rim C Set al. Exact algorithms for multilayer topological via minimization.IEEE Trans. CAD, 1989, 8: 1165\u20131173.","journal-title":"IEEE Trans. CAD"},{"key":"BF02948786_CR108","doi-asserted-by":"crossref","unstructured":"Rose N A, Oldfield J V. Printed \u2014 wiring \u2014 board layout by computer.Electronics and Power, Oct. 1971, pp.376\u2013379.","DOI":"10.1049\/ep.1971.0245"},{"key":"BF02948786_CR109","first-page":"212","volume":"101","author":"V B Alekseev","year":"1976","unstructured":"Alekseev V B, Gonchakov V S. Thickness of arbitrary complete graphs.Math. Sbornik, 1976, 101: 212\u2013230.","journal-title":"Math. Sbornik"},{"key":"BF02948786_CR110","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1090\/S0002-9904-1964-11213-1","volume":"70","author":"L Beineke","year":"1964","unstructured":"Beineke L, Harary F. On the thickness of the complete graph.Bull. Amer. Math. Soc., 1964, 70: 618\u2013620.","journal-title":"Bull. Amer. Math. Soc."},{"key":"BF02948786_CR111","doi-asserted-by":"crossref","unstructured":"Beineke L, Harary F. Inequalities involving the genus of a graph and its thickness. InProc. Glasgow Math. Assoc., 1965, 7: 19\u201321.","DOI":"10.1017\/S2040618500035097"},{"key":"BF02948786_CR112","doi-asserted-by":"crossref","first-page":"850","DOI":"10.4153\/CJM-1965-084-2","volume":"17","author":"L Beineke","year":"1965","unstructured":"Beineke L, Harary F. The thickness of the complete graph.Canad. J. Math., 1965, 17: 850\u2013859.","journal-title":"Canad. J. Math."},{"key":"BF02948786_CR113","doi-asserted-by":"crossref","unstructured":"Beineke L, Harary F, Moon J W. On the thickness of the complete bipartite graph. InProc. Camb. Phil. Soc., 1964, 60: 1\u20134.","DOI":"10.1017\/S0305004100037385"},{"issue":"4","key":"BF02948786_CR114","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1109\/TCS.1977.1084323","volume":"24","author":"N K Bose","year":"1977","unstructured":"Bose N K, Prabhu K A. Thickness of graphs with degree constrained vertices.IEEE Trans. Cir. Syst., 1977, Case-24(4): 184\u2013190.","journal-title":"IEEE Trans. Cir. Syst."},{"key":"BF02948786_CR115","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F R K Chung","year":"1987","unstructured":"Chung F R K, Leighton F T, Rosenberg A L. Embedding graphs in books: A graph layout problem with applications to VLSI design.SIAM J. Algeb Discrete Methods, 1987, 8: 33\u201348.","journal-title":"SIAM J. Algeb Discrete Methods"},{"key":"BF02948786_CR116","unstructured":"Hobbs A M. A survey of thickness. InRecent progress in Combinatorics, Tutte W T (ed.), 1969, pp.255\u2013264."},{"key":"BF02948786_CR117","doi-asserted-by":"crossref","first-page":"145","DOI":"10.6028\/jres.072B.018","volume":"72B","author":"A M Hobbs","year":"1968","unstructured":"Hobbs A M, Grossman G W. A class of thickness-minimal graphs.J. Res. Nat. Bur. Standards, 1968, 72B: 145\u2013153.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF02948786_CR118","doi-asserted-by":"crossref","first-page":"239","DOI":"10.6028\/jres.072B.023","volume":"72B","author":"A M Hobbs","year":"1968","unstructured":"Hobbs A M, Grossman G W. Thickness and connectivity in graphs.J. Res. Nat. Bur. Standards, 1968, 72B: 239\u2013244.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF02948786_CR119","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R Jayakumar","year":"1989","unstructured":"Jayakumar Ret al O(n 2) algorithms for graph planarization.IEEE Trans. CAD, 1989, 8: 257\u2013267.","journal-title":"IEEE Trans. CAD"},{"key":"BF02948786_CR120","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/S0021-9800(67)80010-3","volume":"3","author":"M Kleinert","year":"1967","unstructured":"Kleinert M. The thickness of then-dimensional cube.J. Comb, Theory, 1967, 3: 10\u201315.","journal-title":"J. Comb, Theory"},{"key":"BF02948786_CR121","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF02576900","volume":"1","author":"F Lerda","year":"1964","unstructured":"Lerda F, Majoranic E. An algorithm for connectingn points with a minimum number of crossings.Calcolo, 1964, 1: 257\u2013365.","journal-title":"Calcolo"},{"key":"BF02948786_CR122","unstructured":"Levow R B. On Tutte\u2019s algebraic approach to the theory of crossing numbers. InProc. 3-rd S-E Conf. Comb. Graph Theory Comput., 1972, pp.315\u2013324."},{"key":"BF02948786_CR123","unstructured":"Lin P M. On Methods of deleting planar graphs. InProc. 8-th Midwest Symp. Cir. Theory, Colorado State Univ., Boulder, 1965, pp.11\u201319"},{"issue":"4","key":"BF02948786_CR124","first-page":"32","volume":"2","author":"T Y Liu","year":"1998","unstructured":"Liu T Y, Liu Y P. On the crossing number of circular graphs.OR Transactions, 1998, 2(4): 32\u201338.","journal-title":"OR Transactions"},{"key":"BF02948786_CR125","unstructured":"Liu Y P. Boolean approaches to graph embeddings related to VLSI.Discrete Applied Math., accepted and to appear."},{"key":"BF02948786_CR126","unstructured":"Liu Y P. Planarity theory and routing automation. Plenary Report, Symposium on Mathematical Mechanization, Beijing, 1999 (in Chinese)."},{"key":"BF02948786_CR127","first-page":"1087","volume":"10","author":"A N Melikhov","year":"1972","unstructured":"Melikhov A N, Kuleychik V M, Lisyak V V. Partition of a graph into plane subgraphs (in Rassian).Cybernetics, 1972, 10: 1087\u20131090.","journal-title":"Cybernetics"},{"issue":"3","key":"BF02948786_CR128","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/jgt.3190120308","volume":"12","author":"B Richter","year":"1988","unstructured":"Richter B. Cubic graphs with crossing number two.J. Graph Theory, 1988, 12(3): 363\u2013374.","journal-title":"J. Graph Theory"},{"key":"BF02948786_CR129","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02575825","volume":"11","author":"F Rubin","year":"1974","unstructured":"Rubin F. A note on Lerda and Majoronic\u2019s minimum corssing algorithm.Calcolo, 1974, 11: 201\u2013203.","journal-title":"Calcolo"},{"key":"BF02948786_CR130","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis M. Embedding planar graphs in four pages.J. Comput. Syst. Sci., 1989, 38: 36\u201367.","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"BF02948786_CR131","first-page":"229","volume":"12","author":"L Auslander","year":"1963","unstructured":"Auslander L, Brown T, Youngs J W T. The embedding of graphs in manifolds.J. Math. Mech., 1963, 12(4): 229\u2013234.","journal-title":"J. Math. Mech."},{"key":"BF02948786_CR132","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF02664795","volume":"11","author":"Y P Liu","year":"1996","unstructured":"Liu Y P. Transportation networks: Old and new.Applied Math., (JCU), 1996, B11: 251\u2013272.","journal-title":"Applied Math., (JCU)"},{"key":"BF02948786_CR133","volume-title":"Transportation Networks: Theory and Methods","author":"Y P Liu","year":"1998","unstructured":"Liu Y P. Transportation Networks: Theory and Methods. Shanghai Jiaotong University Press, Shanghai, 1998 (in Chinese)."},{"key":"BF02948786_CR134","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1109\/43.46784","volume":"9","author":"M Kaufmann","year":"1990","unstructured":"Kaufmann M. A linear time algorithm for routing in a convex grid.IEEE Trans. CAD, 1990, 9: 180\u2013184.","journal-title":"IEEE Trans. CAD"},{"key":"BF02948786_CR135","unstructured":"Lawrencenko S, Liu X, Liu Y P. An algorithm for constructing a rectilinear embedding of a given graph in the plane (with Lawrencenko S, Liu X).Comb. Graph Theory\u201995, World Scien. Pub., 1995, pp.205\u2013217."},{"key":"BF02948786_CR136","doi-asserted-by":"crossref","unstructured":"Storer J A. The node cost measure for embedding graphs in the planar grid. InProc. 12-th ACM Symp. Comput., 1980, pp.201\u2013210.","DOI":"10.1145\/800141.804667"},{"key":"BF02948786_CR137","volume-title":"Enumerative Theory of Maps","author":"Y P Liu","year":"1999","unstructured":"Liu Y P Enumerative Theory of Maps. Kluwer, Dordrecht\/Boston\/London, 1999."}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02948786.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02948786\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02948786","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T11:50:18Z","timestamp":1631793018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02948786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,9]]},"references-count":137,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1999,9]]}},"alternative-id":["BF02948786"],"URL":"https:\/\/doi.org\/10.1007\/bf02948786","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"value":"1000-9000","type":"print"},{"value":"1860-4749","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,9]]}}}