Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Orthogonal drawings of graphs for the automation of VLSI circuit design

  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

Abstract

This article shows the recent developments on orthogonal drawings of graphs which have applications for the automation of VLSI circuit design. Meanwhile, a number of problem are posed for further research.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Kuratowski K. Sur le Problem des Coubes Gauches en Topologie.Fund. Math., 1930, 15: 271–283.

    MATH  Google Scholar 

  2. MacLane S. A structural characterization of planar combinatorial graphs.Duke Math. J., 1937, 3: 460–472.

    Article  MATH  MathSciNet  Google Scholar 

  3. MacLane S. A combinatorial condition for planar graphs.Fund. Math., 1937, 28: 22–32.

    MATH  Google Scholar 

  4. Whitney H. Non-separable and planar graph.Trans. AMS, 1932, 34: 339–162.

    Article  MathSciNet  Google Scholar 

  5. Whitney H. Planar graphs.Fund. Math., 1933, 21: 73–84.

    Google Scholar 

  6. Whitney H. On regular closed curves in the plane.Compositio Math., 1937, 4: 276–284.

    MATH  MathSciNet  Google Scholar 

  7. Wu W T. The realization of complexies in the Euclidean space.Acta Math. Sinica, 1955, 5: 505–452 (in Chinese),

    MATH  MathSciNet  Google Scholar 

  8. Wu W T. A theory of Imbedding, Immersion, and Isotopy of Polytopes in an Euclidean Space. Science Press, Beijing, 1965.

    Google Scholar 

  9. Wu W T. Planar embedding of linear graphs.Sci. Bull. (KEXUETONGBAO), 1974, 19(2): 226–228 (in Chinese).

    Google Scholar 

  10. Wu W T. Rational Homotopy Type. Lect. Notes in Math. 1246, Springer, New York/Heidelberg/Berlin, 1987.

    MATH  Google Scholar 

  11. Wu W T. Mathematical problems in the design of integrated circuits.Math. Theory Practice, 1973, 1: 20–40 (in Chinese).

    Google Scholar 

  12. Wu W T. On the planar embedding of linear graphs I.J. Syst. Sci. Math, 1985, 5: 290–320.

    MATH  Google Scholar 

  13. Wu W T. On the planar embedding of linear graphs II.J. Syst. Sci. Math., 1986, 6: 23–35.

    MATH  Google Scholar 

  14. Wu W T. The Realization of Polytopes in the Euclidean Space. Science Press, Beijing, 1978 (in Chinese).

    Google Scholar 

  15. Wu W T. Selected Papers of Wu Wenjun. Shandong Education Press, Jinan, 1986 (in Chinese).

    Google Scholar 

  16. Wu W T. On Mathematical Mechanization on by Wu Wenjun. Shandong Education Press, Jinan, 1995 (in Chinese).

    Google Scholar 

  17. Liu Y P. Embeddability Theory of Graphs. Science Press, Beijing, 1994, (in Chinese).

    Google Scholar 

  18. Liu Y P. Embeddability in Graphs. Kluwer, Dordrecht/Boston/London, 1995.

    MATH  Google Scholar 

  19. Tutte W T. A class of Abelian groups.Canad. J. Math., 1956, 8: 13–28.

    MATH  MathSciNet  Google Scholar 

  20. Tutte W T. Toward a theory of crossing numbers.J. Comb. Theory, 1970, 8: 45–53.

    Article  MATH  MathSciNet  Google Scholar 

  21. Liu Y P. Module 2 programming and planar embedding.Acta Math. Appl Sinica, 1978, 1: 395–406 (in Chinese).

    Google Scholar 

  22. 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–434.

  23. 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–265.

  24. Rosenstiehl P. Preuve algebrique du critere de planarite de Wu(Wenjun)-Liu(Yanpei).Ann. Discrete Math., 1980, 9: 67–78.

    Article  MATH  MathSciNet  Google Scholar 

  25. Cook S A. The complexity of theorem proving procedures. InProc. 3rd ACM Symp. Comput., 1971, pp.151–158.

  26. Garey M R, Johnson D S. Computer and Intractability-A Guide to the Theory of NP-Completeness, Freeman W H (eds.), San Francisco, 1979.

  27. Lipton R J, Tarjan R E. A separator theorem for planar graphs.SIAM J. Appl. Math., 1979, 36: 177–189.

    Article  MATH  MathSciNet  Google Scholar 

  28. Lipton R J, Tarjan R E. Applications of a planar separator theorem.SIAM J. Comput., 1980, 9: 615–627.

    Article  MATH  MathSciNet  Google Scholar 

  29. Liu Y P. Theory of Rectilinear Layouts. China Railway Publishing House, Beijing, 1997 (in Chinese).

    Google Scholar 

  30. Hopcroft J, Tarjan R. Isomorphism of planar graphs. InComplexity of Computer Computations, Miller Ret al. (eds.), Plenum, 1972, pp.131–152.

  31. Hopcroft J, Tarjan R. Dividing a graph into triconnected components.SIAM J. Comput., 1973, 2: 135–158.

    Article  MathSciNet  Google Scholar 

  32. Hopcroft J, Tarjan R. Efficient planarity testing.J. ACM., 1974, 21: 549–568.

    Article  MATH  MathSciNet  Google Scholar 

  33. Auslander L, Parter S V. On imbedding graphs in sphere.J. Math. Mech., 1961, 10: 517–523.

    MATH  MathSciNet  Google Scholar 

  34. Becker B, Hotz G. On the optimal layout of planar graphs with fixed boundary.SIAM J. Comput., 1987, 16: 946–972.

    Article  MATH  MathSciNet  Google Scholar 

  35. Dambit Ja. Embedding of a graph into the plane.Latvian Math., 1966, Yearbook 2: 79–93.

    MATH  MathSciNet  Google Scholar 

  36. Demoucron G, Malgrange Y, Pertuiset R. Graphe planaires, reconnaissance et construction de representations planaires topologiques.Rev. Francaise Recherche Operationnelle, 1964, 8: 33–47.

    Google Scholar 

  37. Deo N. Note on Hopcroft and Tarjan’s planarity algorithm.J. ACM, 1976, 33: 74–75.

    Article  MathSciNet  Google Scholar 

  38. Engle W L. An algorithm for embedding graphs in the plane with certain constraints.IEEE Trans. Cir. Theory, 1970, CT-17: 250–252.

    Article  Google Scholar 

  39. 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–263.

    Google Scholar 

  40. Goldstein A J, Schweikert D G. A proper model for testing the planarity of electrical circuits.Bell Syst. Tech. J., 1973, 52: 135–142.

    MathSciNet  Google Scholar 

  41. 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–196.

  42. Hopcroft J, Tarjan R. Planarity testing inV logV steps: Extended abstract. InProc. IFIP Cong., 1971, pp.85–90.

  43. Hope A K. A planar graph drawing program.Solfware-Practice and Experience, 1971, 1: 82–91.

    Google Scholar 

  44. Hotz G. The embedding of graphs in the 2-sphere.Z. Angew. Math. Mech., 1965, 45.

  45. Hotz G. Embedding of graphs in the plane.Math. Ann., 1966 167: 214–223.

    Article  MATH  MathSciNet  Google Scholar 

  46. Inukai T, Weinberg L. Planar, coplanar, and totally planarn-port networks.IEEE Trans. Cir. Syst., 1976, Case-23.

  47. 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–344.

    Article  MATH  MathSciNet  Google Scholar 

  48. Kirkpatrick D G. Optimal search in planar subdivision.SIAM J. Comput., 1983, 12: 28–35.

    Article  MATH  MathSciNet  Google Scholar 

  49. Knauer B. Normalformen planar graphen I.Computing, 1972, 10: 121–136.

    Article  MATH  MathSciNet  Google Scholar 

  50. Knauer B. Normalformen planar graphen II.Computing, 1972, 10: 137–152.

    Article  MATH  MathSciNet  Google Scholar 

  51. Knauer B. A simple planarity criterion.J. ACM, 1975, 22: 226–230.

    Article  MATH  MathSciNet  Google Scholar 

  52. Lefschetz S. Planar graphs and related topics. InProc. Nat. Acad. Sci. 1965, 54: 1763–1765.

  53. 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.

  54. Lenganer T. Hierarchical planarity testing algorithms.J. ACM., 1989, 36: 474–509.

    Article  Google Scholar 

  55. Plesnevic G S. Embedding a graph in the plane.Vycislitellnyes Sistemy, 1963, 6: 45–53.

    MathSciNet  Google Scholar 

  56. Rosenstiehl P. Caracterisation des graphes planaires par une diagonale absreacte.Cong. Numer., 1976, 15: 521–527.

    MathSciNet  Google Scholar 

  57. Rubin F. An algorithm for testing the planarity of a graph.IEEE Computer Group Respositery, R74-73, 1974.

  58. Rubin F. An improved algorithm for testing the planarity of a graph.IEEE Trans. on Computers, 1975, C-24: 113–121.

    Article  MATH  Google Scholar 

  59. Tutte W T. How to draw a graph. InProc. London Math. Soc., 1963, 13(Ser.3): 743–768.

  60. Ulrich J W. A computational theory of planar embedding. InPh. D. Thesis, Univ. Texas, Austin, 1968.

  61. Ulrich J W. A characterization of planar oriented graphs.SIAM J. Appl. Math., 1970, 18: 364–371.

    Article  MATH  MathSciNet  Google Scholar 

  62. Unger P. A theorem on planar graph, components, and subgraphs.J. London Math. Soc., 1951, 26: 256–262.

    Article  MathSciNet  Google Scholar 

  63. Weinberg L. Two new characterization of planar graphs. InProc. 5-th Allerton Conf. Cir. Syst., Uni. Ill., 1967.

  64. Williamson S G. Embedding graphs in the plane-Algorithm aspects.Am. Discrete Math., 1980, 6: 349–384.

    Article  MATH  MathSciNet  Google Scholar 

  65. Wing O. On drawing a planar graph.IEEE Trans. Cir. Theory 1966, 13: 112–114.

    MathSciNet  Google Scholar 

  66. Liu Y P, Marchioro P, Petreschi R. At most single-bend embeddings of cubic graphs. Research Report SI-92/01. Dept. Computer Science, Uni. «La Sapienza” of Rome, 1992. Also inApplied Math. (A J. Chinese Unis.), 1994, B9: 127–142.

  67. 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 “La Sapienza”, 1990; Also inActa Math. Appl. Sinica, Eng., 1992, Series 8: 188–192.

  68. 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–1055.

    Google Scholar 

  69. Liu Y P, Morgana A. Simeone B. On the general theoretical results for rectilinear embeddability of graphs.KEXUE TONGBAO, (Chinese Ed.) 1990, 35: 1513–1514. Or seeChinese Science Bulletin (English Ed.), 1991, 36: 1490.

  70. 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 «La Sapienza», 1990; AlsoinActa Math. Appl. Sinica, Eng., 1991, Series 7: 187–192.

  71. 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. «La Sapienza», Rome, 1993. Also inDiscrete Appl. Math., 1998, 81: 69–92.

  72. 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–400.

  73. 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.

  74. 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.

  75. Liu Y P. On the net-embeddability of graphs.Acta Math. Sinica, 1994, New Series, 8: 413–423.

    Google Scholar 

  76. Liu Y P. On the efficient recognition on the net-extensibility of graphs.Chinese Science Bulletin, 1993, 38: 533–536.

    MATH  Google Scholar 

  77. Liu Y P. Combinatorial optimization arising from VLSI circuit design.Applied Math., (JCU), 1993, B8: 218–235.

    Article  MATH  Google Scholar 

  78. Fraysseix H, Rosentiehl P. A depth — first search characterization of planarity.Ann. Discrete Math., 1982, 13: 75–80.

    MATH  Google Scholar 

  79. Fraysseix H, Rosenstiehl P. A characterization of planar graphs by Tremaux order.Combinatorica, 1985, 5: 127–155.

    Article  MATH  MathSciNet  Google Scholar 

  80. Liu Y P. Planarity testing nd planar embeddings of graphs.Acta Math. Appl. Sinica, 1979, 2: 350–365 (in Chinese).

    MathSciNet  Google Scholar 

  81. 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–329.

  82. 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–79.

  83. Liu Y P. Boolean characterizations of planarity and planar embeddings of graphs.Ann. Operations Research, 1990, 24: 165–174.

    Article  MATH  Google Scholar 

  84. 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–37.

    Google Scholar 

  85. Sun X R. Wu (Wenjun)-Liu (Yanpei) Theorem and planarity testing of graphs.Thesis, Inst. Applied Math., Acad. Sinica, 1987 (in Chinese).

  86. Xu W X. An efficient algorithm for planarity testing based on Wu (Wenjun)-Liu (Yanpei)’s criterion. InProc. 1-st China-USA Conf. Graph Theory and its Applications, Ann. N. Y. Acad. Sci., 1989, 576: 641–652.

  87. Hopcroft J E, Wong J K. Linear time algorithm for isomorphism of planar graphs (extended abstract). In6-th Ann. ACM Symp. Comput., Seattle, 1974.

  88. Hopcroft J, Tarjan R. A V2 algorithm for determining isomorphism of planar graphs.Inform. Process. Lett. 1971, 1: 32–34.

    Article  MATH  Google Scholar 

  89. Weinberg L. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs.IEEE Trans. Circuit Theory, 1966, CT-13: 142–148.

    MathSciNet  Google Scholar 

  90. Weinberg L. Plane representations and codes for planar graphs. InProc. 3-rd Ann. Allerton Conf. Cir. Syst., 1965, pp.733–744.

  91. Weinberg L. Additional simple codes for planar graphs. InProc. 4-th Allerton Conf. Cir. Syst., 1966.

  92. Basden A, Nichols K G. New topological method for layout printed circuits. InProc. IEEE, 1973, 120(3): 325–328.

  93. Batini C, Talamo M, Tamassia R. Computer aided layout of entity-relationship diagrams.IEEE J. Syst. Software, 1994, 4: 163–173.

    Article  Google Scholar 

  94. Behzao M. A criterion for the planarity of the total graph of a graph. InProc. Cambridge Phil. Soc., 1967, 63: 679–681.

  95. Bhatt S N, Leighton F T. A framework for solving VLSI graph layout problems.J. Comput Syst. Scien., 1984, 28: 300–343.

    Article  MATH  MathSciNet  Google Scholar 

  96. Chen R W, Kajitani Y, Chan S P. A graph- theoretic via minimization algorithm for two — layer printed circuit boards.IEEE Trans. Cir. Syst., 1983, Case-30: 284–299.

    Article  MATH  Google Scholar 

  97. 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–503.

    Google Scholar 

  98. Charke E M, Feng Y. Escher-a geometrical layout system for recursively defined circuits.IEEE Trans. CAD, 1988, 7: 908–918.

    Google Scholar 

  99. van Cleemput W M. Mathematical models for the circuit layout problem.IEEE Trans. Cir. Syst., 1976, Case-23(12): 759–767.

    Article  Google Scholar 

  100. 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.

  101. Cohoon J P, Heck P L. BEAVER: a computational geometry based tool for switchbox routing.IEEE Trans. CAD, 1988, 7: 684–697.

    Google Scholar 

  102. Cong J, Wong D F, Liu C L. A new approach to three or four layer channel routing.IEEE Trans. CAD, 1988, 7: 1094–1104.

    Google Scholar 

  103. Du D Z, Liu Y P. Combinatorial Optimization. Handbook of OR Fundamentals. Hui Get al. (eds.), Science Press, Beijing, 1995, pp.125–167.

    Google Scholar 

  104. Hu T C, Kuh S E. Theory and concepts of circuit layout. InVLSI Circuit Layout: Theory and Design. IEEE Press, 1985, pp.3–18.

  105. Lefschetz S. Applications of Algebraic Topology: Graphs and Networks, Springer, New York/Heidelberg/ Berlin, 1975.

    MATH  Google Scholar 

  106. Liu Y P. Rectilinear Embeddings: Theory and Methods. Beijing: Science Press, 1994 (in Chinese).

    Google Scholar 

  107. Rim C Set al. Exact algorithms for multilayer topological via minimization.IEEE Trans. CAD, 1989, 8: 1165–1173.

    Google Scholar 

  108. Rose N A, Oldfield J V. Printed — wiring — board layout by computer.Electronics and Power, Oct. 1971, pp.376–379.

  109. Alekseev V B, Gonchakov V S. Thickness of arbitrary complete graphs.Math. Sbornik, 1976, 101: 212–230.

    Google Scholar 

  110. Beineke L, Harary F. On the thickness of the complete graph.Bull. Amer. Math. Soc., 1964, 70: 618–620.

    Article  MATH  MathSciNet  Google Scholar 

  111. Beineke L, Harary F. Inequalities involving the genus of a graph and its thickness. InProc. Glasgow Math. Assoc., 1965, 7: 19–21.

  112. Beineke L, Harary F. The thickness of the complete graph.Canad. J. Math., 1965, 17: 850–859.

    MATH  MathSciNet  Google Scholar 

  113. Beineke L, Harary F, Moon J W. On the thickness of the complete bipartite graph. InProc. Camb. Phil. Soc., 1964, 60: 1–4.

  114. Bose N K, Prabhu K A. Thickness of graphs with degree constrained vertices.IEEE Trans. Cir. Syst., 1977, Case-24(4): 184–190.

    Article  MATH  MathSciNet  Google Scholar 

  115. 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–48.

    Article  MATH  MathSciNet  Google Scholar 

  116. Hobbs A M. A survey of thickness. InRecent progress in Combinatorics, Tutte W T (ed.), 1969, pp.255–264.

  117. Hobbs A M, Grossman G W. A class of thickness-minimal graphs.J. Res. Nat. Bur. Standards, 1968, 72B: 145–153.

    MathSciNet  Google Scholar 

  118. Hobbs A M, Grossman G W. Thickness and connectivity in graphs.J. Res. Nat. Bur. Standards, 1968, 72B: 239–244.

    MathSciNet  Google Scholar 

  119. Jayakumar Ret al O(n 2) algorithms for graph planarization.IEEE Trans. CAD, 1989, 8: 257–267.

    Google Scholar 

  120. Kleinert M. The thickness of then-dimensional cube.J. Comb, Theory, 1967, 3: 10–15.

    Article  MATH  MathSciNet  Google Scholar 

  121. Lerda F, Majoranic E. An algorithm for connectingn points with a minimum number of crossings.Calcolo, 1964, 1: 257–365.

    Article  MATH  MathSciNet  Google Scholar 

  122. Levow R B. On Tutte’s algebraic approach to the theory of crossing numbers. InProc. 3-rd S-E Conf. Comb. Graph Theory Comput., 1972, pp.315–324.

  123. Lin P M. On Methods of deleting planar graphs. InProc. 8-th Midwest Symp. Cir. Theory, Colorado State Univ., Boulder, 1965, pp.11–19

  124. Liu T Y, Liu Y P. On the crossing number of circular graphs.OR Transactions, 1998, 2(4): 32–38.

    Google Scholar 

  125. Liu Y P. Boolean approaches to graph embeddings related to VLSI.Discrete Applied Math., accepted and to appear.

  126. Liu Y P. Planarity theory and routing automation. Plenary Report, Symposium on Mathematical Mechanization, Beijing, 1999 (in Chinese).

  127. Melikhov A N, Kuleychik V M, Lisyak V V. Partition of a graph into plane subgraphs (in Rassian).Cybernetics, 1972, 10: 1087–1090.

    Google Scholar 

  128. Richter B. Cubic graphs with crossing number two.J. Graph Theory, 1988, 12(3): 363–374.

    Article  MATH  MathSciNet  Google Scholar 

  129. Rubin F. A note on Lerda and Majoronic’s minimum corssing algorithm.Calcolo, 1974, 11: 201–203.

    Article  MATH  MathSciNet  Google Scholar 

  130. Yannakakis M. Embedding planar graphs in four pages.J. Comput. Syst. Sci., 1989, 38: 36–67.

    Article  MATH  MathSciNet  Google Scholar 

  131. Auslander L, Brown T, Youngs J W T. The embedding of graphs in manifolds.J. Math. Mech., 1963, 12(4): 229–234.

    MathSciNet  Google Scholar 

  132. Liu Y P. Transportation networks: Old and new.Applied Math., (JCU), 1996, B11: 251–272.

    Article  MATH  Google Scholar 

  133. Liu Y P. Transportation Networks: Theory and Methods. Shanghai Jiaotong University Press, Shanghai, 1998 (in Chinese).

    Google Scholar 

  134. Kaufmann M. A linear time algorithm for routing in a convex grid.IEEE Trans. CAD, 1990, 9: 180–184.

    MathSciNet  Google Scholar 

  135. 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’95, World Scien. Pub., 1995, pp.205–217.

  136. Storer J A. The node cost measure for embedding graphs in the planar grid. InProc. 12-th ACM Symp. Comput., 1980, pp.201–210.

  137. Liu Y P Enumerative Theory of Maps. Kluwer, Dordrecht/Boston/London, 1999.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Northern Jiaotong University, 100044, Beijing, P.R. China

    Liu Yanpei

Authors
  1. Liu Yanpei
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liu Yanpei.

Additional information

LIU Yanpei is a Professor of Northern Jiaotong University. His research work are mainly on the theory of enumerating maps on surfaces and combinatorial optimization related to graphs, networks and Boolean functions especially appearing in VLSI circuit designs and CAD.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, Y. Orthogonal drawings of graphs for the automation of VLSI circuit design. J. Comput. Sci. & Technol. 14, 447–459 (1999). https://doi.org/10.1007/BF02948786

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02948786

Keywords

Search

Navigation