A linear algorithm to find a rectangular dual of a planar triangulated graph
AlgorithmicaPublished 1 November 1988
Jayaram Bhasker, Sartaj Sahni
Citations99
SJR quartileQ1
SJR score0.97
SNIP1.11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
AnO(n) algorithm is developed to construct a rectangular dual of ann-vertex planar triangulated graph and it is shown that this dual can be implemented as a discrete-time polynomial.
Abstract
We develop anO(n) algorithm to construct a rectangular dual of ann-vertex planar triangulated graph.
Keywords
Computer Science
Computer Science Press eBooksFundamentals of Data Structures in Pascal
227 Citations1984Ellis Horowitz, Sartaj Sahni
This has long been the text of choice for sophomore/junior level data structure courses as well as more advanced courses-no other book offers greater depth or thoroughness.
Design Automation ConferenceAn Algorithm for Finding a Rectangular Dual of a Planar Graph for Use in Area Planning for VLSI Integrated Circuits
79 Citations1984Krzysztof Koźmiński, E. Kinnen
NetworksA linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph
73 Citations1987Jayaram Bhasker, Sartaj Sahni
On developpe un algorithme en temps lineaire pour determiner si un graphe planaire triangule donne possede un dual rectangulaire.
London School of Economics and Political Science Research Online (London School of Economics and Political Science)The planar package planner for system designers
67 Citations1982W. R. Heller, Sorkin, Gregory B. +1 more
19th Design Automation ConferenceOn finding Most Optimal Rectangular Package Plans
63 Citations1982Klim Maling, W. R. Heller +1 more
21st Design Automation Conference ProceedingsAn Algorithm for Finding a Rectangular Dual of a Planar Graph for Use in Area Planning for VLSI Integrated Circuits
52 Citations1984Krzysztof Koźmiński, E. Kinnen
An O(n /sup 2/) algorithm for finding a rectangular dual of a planar triangulated graph is presented and is useful for solving area planning problems in VLSI IC design.
19th Design Automation ConferenceThe Planar Package Planner for System Designers
30 Citations1982W. R. Heller, K. Maling +1 more