_:Nffb08895bdfa4d9a88ae723de3fe76bb "2" .
"Abstract\nWe study the properties of Schnyder\u2019s realizers and canonical ordering trees of plane graphs. Based on these newly \ndiscovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First, we show that G has a\nvisibility representation with height at most \u2308 15n/16 \u2309. This improves the previous best bound\nof (n - 1). Second, we show that every plane graph G has a straight-line grid\nembedding on an (n - \u03B40 - 1) \u00D7 (n - \u03B40 - 1) grid, where \u03B40 is the number of cyclic faces of G with respect to its\nminimum realizer. This improves the previous best bound of (n - 1) \u00D7 (n - 1). \nWe also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these\nproperties, we show that every such a graph has a canonical ordering tree with at most \u2308 (n + 1)/2 \u2309 leaves.\nThis improves the previously known bound of \u230A (2n + 1)/3 \u230B. \nWe show that every 4-connected plane graph has a visibility\nrepresentation with height at most \u2308 3n/4 \u2309.\nAll drawings discussed in this paper can be obtained in linear time." .
"leaves" .
"Mathematical Sciences" .
_:N0ae48d7b4df44ec0854978a6598cbe34 "33" .
_:N2f026819ede04968bf75fc88df91d29e "dimensions_id" .
"2005-01-14" .
"grid" .
.
"straight-line grid" .
"Zhang" .
"canonical ordering tree" .
"minimum realizer" .
"en" .
"1432-0444" .
.
_:N069c98ea011a4425ac6ee2c25925e705 .
"applications" .
"Discrete & Computational Geometry" .
"\u03940" .
"respect" .
"realizers" .
.
"ordering trees" .
"labeling" .
"edge labeling" .
.
_:N18923cbd878b4ca6a7af9cc5ef8ac589 .
.
_:N18923cbd878b4ca6a7af9cc5ef8ac589 "Springer Nature - SN SciGraph project" .
"graph drawing" .
"Xin" .
_:Nffb08895bdfa4d9a88ae723de3fe76bb .
"representation" .
.
"time" .
_:N0ae48d7b4df44ec0854978a6598cbe34 .
.
_:N069c98ea011a4425ac6ee2c25925e705 .
"compact drawings" .
"graph" .
_:N00509d9e807e4acfa91695ada7770a74 .
"height" .
_:N00509d9e807e4acfa91695ada7770a74 "doi" .
.
"2005-01-14" .
"Schnyder\u2019s realizers" .
"321-344" .
.
.
"Springer Nature" .
_:N4ab149e2b773483bb90d1e4dfdef6357 .
_:N069c98ea011a4425ac6ee2c25925e705 _:N4ab149e2b773483bb90d1e4dfdef6357 .
"true"^^ .
"plane triangulations" .
"drawings" .
"face" .
"trees" .
"regular edge labeling" .
.
_:N2f026819ede04968bf75fc88df91d29e .
"https://scigraph.springernature.com/explorer/license/" .
"visibility representation" .
_:N0ae48d7b4df44ec0854978a6598cbe34 .
"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA" .
"https://doi.org/10.1007/s00454-004-1154-y" .
.
"Huaming" .
_:N2f026819ede04968bf75fc88df91d29e .
"vertices" .
.
.
"graph G" .
_:N2f026819ede04968bf75fc88df91d29e "pub.1021220162" .
"Canonical Ordering Trees and Their Applications in Graph Drawing" .
"Pure Mathematics" .
_:Nffb08895bdfa4d9a88ae723de3fe76bb .
"2022-01-01T18:14" .
"He" .
"triangulation" .
"paper" .
.
_:N00509d9e807e4acfa91695ada7770a74 "10.1007/s00454-004-1154-y" .
"article" .
"plane graph G" .
.
_:N4ab149e2b773483bb90d1e4dfdef6357 .
.
"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA" .
"visibility" .
"cyclic faces" .
_:N18923cbd878b4ca6a7af9cc5ef8ac589 .
"linear time" .
"properties" .
.
"0179-5376" .
"plane graph" .
_:N00509d9e807e4acfa91695ada7770a74 .
.
"articles" .
"number" .
"style" .