@inproceedings{242d70901b7d423e893eea6d771ac2c6,
title = "Two algorithms for finding rectangular duals of planar graphs",
abstract = "We present two linear-time algorithms for computing a regular edge labeling of 4-connected planar triangular graphs. This labeling is used to compute in linear time a rectangular dual of this class of planar graphs. The two algorithms are based on totally different frameworks, and both are conceptually simpler than the previous known algorithm and are of independent interests. The first algorithm is based on edge contraction. The second algorithm is based on the canonical ordering. This ordering can also be used to compute more compact visibility representations for this class of planar graphs.",
author = "Goos Kant and Xin He",
note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993 ; Conference date: 16-06-1993 Through 18-06-1993",
year = "1994",
doi = "10.1007/3-540-57899-4\_69",
language = "English",
isbn = "9783540578994",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "396--410",
editor = "\{van Leeuwen\}, Jan",
booktitle = "Graph-Theoretic Concepts in Computer Science - 19th International Workshop, WG 1993, Proceedings",
address = "Germany",
}