"interest" .
"2022-01-01T19:13" .
"https://doi.org/10.1007/3-540-57899-4_69" .
"planar triangular graphs" .
_:N24403ebba36747a0886ba6637a859cfb .
"triangular graph" .
_:Nb84b457cfcd44de894a552086f357719 .
_:N50493ae7428241ac9201f5b3f46c67e9 "10.1007/3-540-57899-4_69" .
"Information and Computing Sciences" .
_:Nf7a7dc8aa13e4e21b77888ba84704581 "Leeuwen" .
_:N50493ae7428241ac9201f5b3f46c67e9 .
"He" .
.
"linear time" .
"framework" .
"planar graphs" .
.
"Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA" .
"representation" .
.
.
.
_:N0643f0d5c7a644c3833ad484c91f4a5b "978-3-540-48385-4" .
_:Nb84b457cfcd44de894a552086f357719 .
"Two algorithms for finding rectangular duals of planar graphs" .
"Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA" .
_:Nf216ebf434e54a58a38c8a64830b424f .
"Department of Computer Science, Utrecht University, Padualaan 14, 3584, CH Utrecht, the Netherlands" .
"regular edge labeling" .
"chapter" .
_:N150a942484ba4e5a828fba6b28fc3bb4 .
"Goos" .
_:Ndf57d9dba55d4f76882ff31733aa5906 "Springer Nature - SN SciGraph project" .
_:N0643f0d5c7a644c3833ad484c91f4a5b "Graph-Theoretic Concepts in Computer Science" .
.
.
"396-410" .
_:N50493ae7428241ac9201f5b3f46c67e9 .
"different frameworks" .
"Computation Theory and Mathematics" .
.
_:Nf7a7dc8aa13e4e21b77888ba84704581 .
.
_:N0643f0d5c7a644c3833ad484c91f4a5b .
.
.
"edge labeling" .
"dual" .
"Compact Visibility Representation" .
"Department of Computer Science, Utrecht University, Padualaan 14, 3584, CH Utrecht, the Netherlands" .
_:Nf7a7dc8aa13e4e21b77888ba84704581 "Jan" .
"linear-time algorithm" .
_:N9f31f81af7054109b1515dfc15c40212 .
_:Nf216ebf434e54a58a38c8a64830b424f "dimensions_id" .
.
"labeling" .
_:Ndf57d9dba55d4f76882ff31733aa5906 .
"algorithm" .
"chapters" .
"visibility representation" .
.
"independent interest" .
"time" .
"rectangular duals" .
"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." .
"canonical ordering" .
"ordering" .
"en" .
_:N150a942484ba4e5a828fba6b28fc3bb4 .
_:N0643f0d5c7a644c3833ad484c91f4a5b .
"contraction" .
_:Ndf57d9dba55d4f76882ff31733aa5906 .
_:N150a942484ba4e5a828fba6b28fc3bb4 _:Nf7a7dc8aa13e4e21b77888ba84704581 .
_:N0643f0d5c7a644c3833ad484c91f4a5b "978-3-540-57899-4" .
"more compact visibility representations" .
_:N9f31f81af7054109b1515dfc15c40212 _:Nb84b457cfcd44de894a552086f357719 .
"https://scigraph.springernature.com/explorer/license/" .
_:N9f31f81af7054109b1515dfc15c40212 .
.
"graph" .
"edge contraction" .
.
_:N24403ebba36747a0886ba6637a859cfb .
.
"first algorithm" .
"Xin" .
"1994-01-01" .
"1994" .
"class" .
_:N24403ebba36747a0886ba6637a859cfb "Springer Nature" .
"second algorithm" .
"Kant" .
_:Nf216ebf434e54a58a38c8a64830b424f "pub.1018910920" .
_:N50493ae7428241ac9201f5b3f46c67e9 "doi" .
.
.
_:Nf216ebf434e54a58a38c8a64830b424f .
"true"^^ .