×

zbMATH — the first resource for mathematics

A linear algorithm to find a rectangular dual of a planar triangulated graph. (English) Zbl 0635.68074
Summary: We develop an O(n) algorithm to construct a rectangular dual of an n- vertex planar triangulated graph.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Bhasker and S. Sahni, A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph,Networks,17 (1987), 307–317. · Zbl 0672.05025
[2] G. Brebner and D. Buchanan, On compiling structural descriptions to floorplans,Proceedings of the IEEE International Conference on Computer-Aided Design, Santa Clara, 1983, pp. 6–7.
[3] J. Grason, A dual linear graph representation for space filling problem of the floor plan type, inEmerging Methods in Environmental Design and Planning (G. T. Moore, ed.), Proceedings of the design methods group, First International Conference, Cambridge, MA, 1968, pp. 170–178.
[4] W. R. Heller, G. Sorkin, and K. Maling, The planar package planner for system designers,Proceedings of the 19th Design Automation Conference, Las Vegas, 1982, pp. 253–260.
[5] E. Horowitz and S. Sahni,Fundamentals of Data Structures in Pascal, Computer Science Press, Rockville, MD, 1984. · Zbl 0408.68003
[6] K. Kozminski and E. Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits,Proceedings of the 21st Design Automation Conference, Alburquerque, 1984, pp. 655–656.
[7] K. Kozminski and E. Kinnen, Rectangular dual of planar graphs,Networks (submitted). · Zbl 0663.05027
[8] K. Maling, S. H. Mueller, and W. R. Heller, On finding most optimal rectangular package plans,Proceedings of the 19th Design Automation Conference, Las Vegas, 1982, pp. 663–670.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.